2019年3月26日火曜日

ABC 008 C - コイン

ABC 008 C - コイン

任意のコインkkについて確率変数XkX_kXk()=1X_k(表) = 1Xk()=0X_k(裏) = 0と定める。また、コインkkの約数が書かれている(kk自身を除く)コインの数をdkd_kとする。dk=0d_k=0ならE[Xk]=P[Xk=1]=1E[X_k]=P[X_k = 1] = 1である。また、dk>1d_k > 1dkd_kが偶数なら
E[Xk]=(N1dk)!dk!N!p=1N(p10)(Npdk)+(p12)(Npdk2)+...+(p1dk)(Np0) \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}
であり、dkd_kが奇数なら
E[Xk]=(N1dk)!dk!N!p=1N(p10)(Npdk)+(p12)(Npdk2)+...+(p1dk1)(Np1) \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}
である。ただし、nmn \le mのとき(nm)=0\binom{n}{m}=0とする。求める期待値はE[Xk]=E[Xk]E[\sum X_k] = \sum E[X_k]なので、そのまま計算できる。64ビット整数に収まらないのでdouble floatを使った。計算量はdouble floatに収まる範囲ではO(N2){\mathcal O}(N^2)

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