ABC 008 C - コイン

• 問題
• AC

任意のコイン$k$について確率変数$X_k$を$X_k(表) = 1$、$X_k(裏) = 0$と定める。また、コイン$k$の約数が書かれている（$k自身$を除く）コインの数を$d_k$とする。$d_k=0$なら$E[X_k]=P[X_k = 1] = 1$である。また、$d_k > 1$で$d_k$が偶数なら
$\begin{aligned} E[X_k] = \frac{(N-1-d_k)!d_k!}{N!} \sum_{p=1}^N &\binom{p-1}{0}\binom{N-p}{d_k} + \binom{p-1}{2}\binom{N-p}{d_k-2} + \\ & ... + \binom{p-1}{d_k}\binom{N-p}{0} \end{aligned}$
であり、$d_k$が奇数なら
$\begin{aligned} E[X_k] = \frac{(N-1-d_k)!d_k!}{N!} \sum_{p=1}^N & \binom{p-1}{0}\binom{N-p}{d_k} + \binom{p-1}{2}\binom{N-p}{d_k-2} + \\ & ... + \binom{p-1}{d_k-1}\binom{N-p}{1} \end{aligned}$
である。ただし、$n \le m$のとき$\binom{n}{m}=0$とする。求める期待値は$E[\sum X_k] = \sum E[X_k]$なので、そのまま計算できる。64ビット整数に収まらないのでdouble floatを使った。計算量はdouble floatに収まる範囲では${\mathcal O}(N^2)$。

解説にははるかに筋の良い考え方が書いてあった。