AT_abc008_3 [ABC008C] コイン

[problemUrl]: https://atcoder.jp/contests/abc008/tasks/abc008_3 高橋君は裏表が区別できる $ N $ 枚のコインを持っている。コインの大きさは異なり、それぞれのコインには $ 1 $ つずつ正の整数が書かれている。 これらのコインを無作為に ($ N! $ 通りの組み合わせがすべて同じ確率で出てくるように) 一列に並べる。その後、以下の手順を実行する。 1. すべてのコインを表向きにする。 2. 左端のコインから順に、現在見ているコインよりも右側 (それ自身を除く) にあるコインのうち、現在見ているコインに書かれている整数の倍数が書かれているコインすべての裏表をひっくり返す。 高橋君はこの操作を終了した後に表を向いているコインの枚数の期待値が知りたい。 あなたは高橋くんの代わりに、期待値を計算するプログラムを作成してほしい。

N/A

N/A

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 8 $ を満たすデータセット $ 1 $ に正解した場合は、$ 99 $ 点が与えられる。 - 追加制約のないデータセット $ 2 $ に正解した場合は、さらに $ 1 $ 点が与えられ、合計で $ 100 $ 点が得られる。 ### Sample Explanation 1 コインには、サイズの小さい方から順にそれぞれ $ 2 $ , $ 4 $ , $ 8 $ という数が書かれています。例えば、$ 3! $ 通りの並べ方のうち、コインが大きさの昇順に並んでいる場合は、以下の手順が行われることになります。 1. 初期状態で、すべてのコインを表に向けるので、コインは左から順に、\\\[`表`, `表`, `表`\\\] となっています。 2. 次に、左から $ 2 $ 番目以降のコインの中で、$ 2 $ の倍数が書かれたコインを探します。左から $ 2 $ 番目のコインと左から $ 3 $ 番目のコインが該当するので、これらのコインを裏返します。その結果、コインは左から順に \\\[`表`, `裏`, `裏`\\\] となります。 3. 次に、左から $ 3 $ 番目以降のコインの中で、$ 4 $ の倍数が書かれたコインを探します。左から $ 3 $ 番目のコインのみが該当するので、このコインを裏返します。その結果、コインは左から順に \\\[`表`, `裏`, `表`\\\] となります。 コインの裏表は下図のように変化します。この図において、白いコインは表向きのコイン、黒いコインは裏向きのコインで表してあります。 !\[\](http://abc008.contest.atcoder.jp/img/abc/008/3-1.png)このように、$ 3!\ =\ 6 $ 通りの並べ方について、それぞれの並べ方での最終状態は下図のようになります。 !\[\](http://abc008.contest.atcoder.jp/img/abc/008/3-2.png)以上より期待値は $ 13/6\ =\ 2.16666666666... $ となります。 ### Sample Explanation 2 どのような順番で並べても、左から順に、\\\[`表`, `裏`, `表`, `裏`\\\] となります。