ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

yukicoder No.1100 Boxes

yukicoder プログラミング競技プログラミング

No.1100 Boxes - yukicoder

解法

まずボールが1つも入っていない箱の数を固定します。これを $a$ とすると、その選び方は $_{K}C_{a}$ 通りです。

その上で、残りの $K-a$ 個の箱全てにボールが入るような場合の数を求めます。これは包除原理を用いて

$\displaystyle\sum_{b=0}^{K-a}(-1)^{b} {}_{K-a}C_{b}(K-a-b)^{N}$

と求めることができます。

先ほどの $_{K}C_{a}$ と合わせて、二項係数を階乗の形にすると、これは結局

$\displaystyle_{K}C_{a}(-1)^{b} {}_{K-a}C_{b}(K-a-b)^{N} = \frac{K!}{a!b!(K-a-b)!}(-1)^{b}(K-a-b)^{N}$

を、 $a=1, 3, 5, ...$ かつ $b=0, 1, ...$ かつ $a+b \le K$ の範囲で全て足し合わせれば良いことになります。

これは2重ループですが、NTTを用いた畳み込みで計算できる形になっています。具体的には先ほどの式を

$\displaystyle f(a) = \frac{1}{a!}$

$\displaystyle g(b) = \frac{(-1)^{b}}{b!}$

$\displaystyle h(s) = \frac{K!}{(K-s)!}(K-s)^{N}$ （ $s = a+b$ とする）

の積として分解できるので、 $f(a)$ と $g(b)$ を畳み込んだ後に $h(s)$ を掛け、 $s \le K$ の範囲で全て合計すれば良いです。

ACコード

#504097 (C++17(1z)) No.1100 Boxes - yukicoder