H - Wines

考察

毒入りワインでないワインを安全なワインと言うことにします。

ワインを飲んだ友達の体調に注目します。もし、その友達が体調を崩さなかったら、飲んだ $L$ 本のワインはすべて安全であることが言えます。一方、その友達が体調を崩したら、飲んだワインの中に毒入りワインが存在します。しかし、毒入りワインは $1$ 本しか存在しないので、飲んでいない $N-L$ 本のワインはすべて安全であることが言えます。

安全だと分かったワインに「安全」というラベルを貼り、最終的に $N-1$ 本のワインが安全だと分かったら、毒入りワインは残った $1$ 本のワインであると特定できます。

逆に、安全かどうか分からないワインが $2$ 本以上あるとしたら、毒入りワインは特定できません。これは、安全かどうか分からないワインのどれが毒入りワインであったとしても、友人の「体調を崩した・崩していない」という情報が全く変わらないからです。

問題の言い換え

「安全なワインを選ぶ」ということを考えると、問題は次のように置き換えられます。

ワイン $2, 3, \cdots, N$ の $N-1$ 本のワインがあると考える。各友達に対して、次を行う：

• タイプ $1, 2$ のいずれか一方を選ぶ。タイプ $1$ を選んだら、次に $N-1$ 本のワインの中から $L$ 本を選ぶ。タイプ $2$ を選んだら、次に $N-1$ 本のワインの中から $N-L$ 本を選ぶ。

最終的に、各ワインが $1$ 本以上選ばれるような方法の個数は何通りか？

包除原理

$N-1$ 本のワインのうち「 $k$ 番目のワインが選ばれない」という $N-1$ 個の条件たちで包除原理を適用することを考えます。

$N-1-i$ 本のワインが選ばれないとすると、 $i$ 本のワインだけが選ばれる権利があります。選ばれる権利がある $i$ 本のワインを固定すると、各友達に対してのワインの選び方は、タイプ $1$ の $\binom{i}{L}$ 通り、タイプ $2$ の $\binom{i}{N-L}$ 通りあります。よって、この場合は

$\displaystyle \left( \binom{i}{L} + \binom{i}{N-L}\right)^M$

通りの選び方があります。包除原理を適用して、答えは

$\displaystyle \sum_{i=1}^{N-1} (-1)^{N-1-i} \binom{N-1}{i} \left( \binom{i}{L} + \binom{i}{N-L}\right)^M$

となります。これは、階乗 mod $998244353$ と、繰り返し二乗法を行うことで $O(N \log M)$ 時間で計算できます。