定義

\(N\) 個の区別がつく物を \(K\) 個順不同で選ぶ場合の数を \(\binom{N}{K}\) と表します。 \(\binom{N}{K}=\frac{N!}{K!(N-k)!}\) となります。

\(f(x)\) の \(x^k\) の係数を \([x^k]f(x)\) と表します。

多項式のテイラーシフトを用いた \(\mathcal{O}(N\log{N})\) 解法

以下、選んだ \(K\) 個に含まれない色の個数を求める事とします。

\(i\) 個選ぶ際の 高橋君がもらうキャンディに色 \(j\) のキャンディが含まれない 確率を \(p_{i,j}\) とします。 色 \(j\)のキャンディが全部で \(n_j\) 個あるとするならば \(p_{i,j}=\binom{N-n_j}{K}/\binom{N}{K}\) ( \(N-n_j>K\) の時は \(0\) ) となります。

現在 \(j=1,2,\cdots,C\) のキャンディが存在するとし、\(i\) 個選ぶ際の 高橋君がもらうキャンディに含まれない色の種類数の期待値を \(E_i\) とします。 \(f(x)=\sum_{i=0}^{N} \binom{N}{i}E_i x^i\) を考える事にすると、期待値の線形性より \(f(x)=\sum_{j=0}^{C} \sum_{i=0}^{N-n_j} \binom{N-n_j}{i}x^i\) となる為、二項定理より \(f(x)=\sum_{j=0}^{C} (1+x)^{N-n_j}\) と書き直せる事がわかります。

ここで、\(g(x)= \sum_{j=0}^C x^{n_j}\) とすると、 \(f(x)=g(x+1)\) となるため、一般に \(f(x)\) から \(f(x+1)\) を高速で求める手法があればこの問題は解ける事がわかります。

\(N\) 次方程式 \(f(x)=\sum_{i=0}^{N} A_i x^i\) に対し、

\[ \begin{aligned} &f(x+1)\\ &=\sum_{i=0}^{N} A_i (x+1)^i\\ &=\sum_{i=0}^{N}\sum_{j=0}^i A_i \binom{i}{j} x^j\\ &=\sum_{i=0}^{N}\sum_{j=0}^i (A_i\times i! \times x^i)\frac{x^{N-1+j-i}}{(i-j)!} \frac{1}{j!}x^{1-N} \end{aligned} \]

となる為、

\[ \begin{aligned} &\sum_{j=0}^{N} \frac{[x^j]f(x+1)}{j!}x^j\\ &=\sum_{i=0}^{N}\sum_{j=0}^i (A_i\times i! \times x^i)\frac{x^{N-1+j-i}}{(i-j)!}x^{1-N}\\ &=\sum_{j=0}^N([x^{N-1+j}](\sum_{i=0}^N A_i \times i! \times x^i)(\sum_{i=0}^{N-1} \frac{x^{N-1-i}}{i!}))x^j \end{aligned} \]

より、この \(f(x)\) から \(f(x+1)\) は多項式乗算を用いて \(\mathcal{O}(N\log{N})\) で解ける事がわかりました

参考(library-checker)