確率変数 \(X_{i,j}\) を「 \(i\) 日目に子ども \(j\) がクッキーをもらえたとき \(1\) 、もらえなかったとき \(0\)」と定めます。求める期待値は \(E\left[\prod_j \sum_i P_{i,j}\right]\) です。

期待値の線形性から

\(\begin{aligned} E\left[\prod_j \sum_i P_{i,j}\right] &= E\left[\sum_{(i_1,i_2\ldots,i_K)}P_{i_1,1}P_{i_2,2}\dots P_{i_K,K}\right]\\ &=\sum_{(i_1,i_2\ldots,i_K)} E\left[P_{i_1,1}P_{i_2,2}\dots P_{i_K,K}\right] (★) \end{aligned}\)

が成り立ちます。

各日の割り当ては別の日の割り当てに影響しないことから、\(i\neq i'\) のとき、任意の \(j,j'\) で \(P_{i,j}\) と \(P_{i',j'}\) は独立です。独立な確率変数の積の期待値は期待値の積であることから、\(i\) ごとに分類することで、

\(\displaystyle E\left[P_{i_1,1}P_{i_2,2}\dots P_{i_K,K}\right]=\prod_i E\left[\prod_{j\in \{m \mid i_m=i\}} P_{i,j} \right]\)

となります。ここで \(\prod_{j\in \{m \mid i_m=i\}} P_{i,j} \) はその”意味”を考えることで「\(i\) 日目に指定された \(\#\{m\mid i_m=i\}\) 人の子どもが全員がクッキーをもらうとき \(1\) 、そうでないとき \(0\) 」であることから、その期待値は \(i\) と \(x_i:=\#\{m\mid i_m=i\}\) のみから \(\displaystyle \frac{\binom{N-x_i}{a_i-x_i}}{\binom{N}{a_i}}\) と定まります。

よって (★) 式において和を取る対象を \((i_1,\ldots,i_N)\) ではなく、その値の分布、即ち \((x_1,\ldots,x_K)\) に取り替えることができます。値の分布が \((x_1,\dots,x_K)\) になるような \((i_1,\dots,i_N)\) は \(\displaystyle \frac{N!}{\prod_i x_i!}\) 個あることから、

\(\begin{aligned} \sum_{(i_1,i_2\ldots,i_K)} E\left[P_{i_1,1}P_{i_2,2}\dots P_{i_K,K}\right] &=\sum_{(i_1,i_2\ldots,i_K)} \prod_i E\left[\prod_{j\in \{m \mid i_m=i\}} P_{i,j} \right]\\ &=\sum_{x_1+\dots+x_K=N} \frac{N!}{\prod_i x_i!}\prod_i \frac{\binom{N-x_i}{a_i-x_i}}{\binom{N}{a_i}}\\ &=N!\left(\prod_i\frac{1}{\binom{N}{a_i}}\right)\left(\sum_{x_1+\dots+x_K=N}\prod_i\frac{\binom{N-x_i}{a_i-x_i}}{x_i!}\right) \end{aligned}\)

となります。

ここで一般に \(\displaystyle \sum_{x_1+\dots+x_K=N}\prod_i f(i,x_i)\) の形の式の値は、
\(\displaystyle \mathrm{dp}[k][n]=\sum_{x_1+\dots+x_k=n}\prod_{i=1}^{k}f(i,x_i)\)
と定める DP により \(O(KN^2)\) で計算することができるため、全体で \(O(KN^2)\) でこの問題を解くことができました。