ABC008 C コイン - 足跡-sokuseki-

数学ができないので。
期待値問題は苦手です。

$N$ 枚のコインを無作為に一列に並べる。左端から順に、そのコインよりも右側にある、そのコインに書かれた数 $C_i$ の倍数が書かれたコインをすべてひっくり返す。最終的に表を向いている(偶数回反転した)コインの枚数の期待値を求めよ。

制約
$1 \le N \le 100$
$1 \le C_i \le 10^9$

期待値は、起こりうる確率を足し合わせることで求められる。よって、各コインについて、並べ方によって表を向く確率を計算して、それを足し合わせるという方針。

今見ているコインをCとすると、Cをひっくり返すことに関わるコインはCの約数が書かれているコインのみである。よって、Cの約数が書かれているコインの数に注目する。

Cが表を向いている(偶数回ひっくり返えす)とき、Cの左側にはCの約数が書かれたコインが偶数枚ある。
このことから、Cの約数が書かれたコインの数をSとすると、
Cが表を向いている場合の数は

となる。
よって、Cが表を向いている確率は

であるので、これを各コインについて足し合わせればよい。

計算量は $O(N^2)$ 。

数学は苦手。
今回は解説を見たけど、期待値問題を自力で解けるようになりたい。