ABC 008 C - コイン
任意のコインkについて確率変数XkをXk(表)=1、Xk(裏)=0と定める。また、コインkの約数が書かれている(k自身を除く)コインの数をdkとする。dk=0ならE[Xk]=P[Xk=1]=1である。また、dk>1でdkが偶数なら
E[Xk]=N!(N−1−dk)!dk!p=1∑N(0p−1)(dkN−p)+(2p−1)(dk−2N−p)+...+(dkp−1)(0N−p)
であり、dkが奇数なら
E[Xk]=N!(N−1−dk)!dk!p=1∑N(0p−1)(dkN−p)+(2p−1)(dk−2N−p)+...+(dk−1p−1)(1N−p)
である。ただし、n≤mのとき(mn)=0とする。求める期待値はE[∑Xk]=∑E[Xk]なので、そのまま計算できる。64ビット整数に収まらないのでdouble floatを使った。計算量はdouble floatに収まる範囲ではO(N2)。
解説にははるかに筋の良い考え方が書いてあった。