AT_s8pc_6_f Random Shuffles

[problemUrl]: https://atcoder.jp/contests/s8pc-6/tasks/s8pc_6_f 新学期も始まり、新しいクラスで交流を行いたいと思った E869120 君は、次のようなカードゲームを考えました。 - $ N $ 枚のカードがあり、$ 1,\ 2,\ 3,...,\ N $ と番号付けられています。 - カードは $ D $ 種類の色のいずれかで塗られており、色は $ 0,\ 1,\ 2,...,\ D-1 $ のいずれかの数で表されます。 - カード $ i $ は色 $ S_i\ (0\ \leq\ S_i\

入力は以下の形式で標準入力から与えられます。 ただし、$ S_1,\ S_2,\ ...,\ S_N $ に関しては、数字をつなげた文字列として与えられます。 > $ N $ $ D $ $ L $ $ S_{1}S_{2}S_{3}S_{4}\ ...\ S_{N} $

$ D $ 行に渡って出力してください。 $ i $ 行目には、プレイヤー $ i $ の $ N\ \div\ D $ 回のゲームの得点の期待値の合計を出力してください。 絶対誤差または相対誤差が $ 10^{-5} $ 未満であれば、正解と見做されます。

### 制約 - $ D $ は $ 3 $ 以上 $ 10 $ 以下の整数 - $ N $ は $ 3 $ 以上 $ 3\ 000\ 000 $ 以下の $ D $ の倍数 - $ L $ は $ 1 $ 以上 $ 1\ 000\ 000\ 000 $ 以下の整数 - $ S_i\ (1\ \leq\ i\ \leq\ N) $ は $ 0,\ 1,\ 2,\ ...,\ D-1 $ のいずれか ### 部分点 この問題はいくつかの小課題に分けられ、その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます。 提出したソースコードの得点は、正解した小課題の点数の合計となります。 1. (50 点)：$ N\ \leq\ 10,\ D\ \leq\ 4,\ L\ =\ 1 $ 2. (70 点)：$ N\ \leq\ 10,\ D\ \leq\ 4,\ L\ \leq\ 5 $ 3. (80 点)：$ N\ \leq\ 50,\ D\ \leq\ 4,\ L\ \leq\ 300 $ 4. (100 点)：$ N\ \leq\ 3\ 000,\ D\ \leq\ 4,\ L\ \leq\ 300 $ 5. (210 点)：$ N\ \leq\ 3\ 000,\ D\ \leq\ 4 $ 6. (130 点)：$ N\ \leq\ 50\ 000,\ D\ \leq\ 4 $ 7. (40 点)：$ N\ \leq\ 150\ 000,\ D\ \leq\ 6 $ 8. (40 点)：$ N\ \leq\ 300\ 000,\ D\ \leq\ 8 $ 9. (40 点)：$ N\ \leq\ 500\ 000,\ D\ \leq\ 10 $ 10. (40 点)：$ N\ \leq\ 800\ 000,\ D\ \leq\ 10 $ 11. (200 点)：$ N\ \leq\ 3\ 000\ 000,\ D\ \leq\ 10 $ ### Sample Explanation 1 カードの並びを最初 $ (1,\ 2,\ 3) $ として、$ L=1 $ 回の問題文中の 3. の操作を繰り返すと、$ (1,\ 3,\ 2),\ (2,\ 1,\ 3),\ (3,\ 2,\ 1) $ の可能性が $ 1/3 $ ずつになります。 それぞれ、プレイヤーの得点は以下の通りです。 - $ (1,\ 3,\ 2) $：プレイヤーの得点はそれぞれ $ 1,\ 0,\ 0 $ - $ (2,\ 1,\ 3) $：プレイヤーの得点はそれぞれ $ 0,\ 0,\ 3 $ - $ (3,\ 2,\ 1) $：プレイヤーの得点はそれぞれ $ 0,\ 2,\ 0 $ よって、プレイヤーの得点の期待値はそれぞれ $ 1/3,\ 2/3,\ 1 $ になります。 ### Sample Explanation 2 $ 1 $ ラウンド目では、次の $ 4 $ 通りが等確率で起こります。 - $ (1,\ 2,\ 4,\ 3) $：プレイヤーの得点はそれぞれ $ 1,\ 2,\ 4,\ 0 $ - $ (1,\ 3,\ 2,\ 4) $：プレイヤーの得点はそれぞれ $ 1,\ 3,\ 0,\ 0 $ - $ (2,\ 1,\ 3,\ 4) $：プレイヤーの得点はそれぞれ $ 0,\ 0,\ 0,\ 0 $ - $ (4,\ 2,\ 3,\ 1) $：プレイヤーの得点はそれぞれ $ 0,\ 2,\ 0,\ 0 $ したがって、$ 1 $ ラウンド目でのそれぞれのプレイヤーの得点の期待値はそれぞれ $ 1/2,\ 7/4,\ 1,\ 0 $ になります。 $ 2 $ ラウンド目では、次の $ 8 $ 通りが等確率で起こります。 - $ (1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 8,\ 7) $：プレイヤーの得点はそれぞれ $ 1,\ 2,\ 0,\ 0 $ - $ (1,\ 2,\ 3,\ 4,\ 5,\ 7,\ 6,\ 8) $：プレイヤーの得点はそれぞれ $ 1,\ 9,\ 0,\ 0 $ - $ (1,\ 2,\ 3,\ 4,\ 6,\ 5,\ 7,\ 8) $：プレイヤーの得点はそれぞれ $ 1,\ 2,\ 0,\ 0 $ - $ (1,\ 2,\ 3,\ 5,\ 4,\ 6,\ 7,\ 8) $：プレイヤーの得点はそれぞれ $ 1,\ 2,\ 0,\ 5 $ - $ (1,\ 2,\ 4,\ 3,\ 5,\ 6,\ 7,\ 8) $：プレイヤーの得点はそれぞれ $ 1,\ 2,\ 4,\ 0 $ - $ (1,\ 3,\ 2,\ 4,\ 5,\ 6,\ 7,\ 8) $：プレイヤーの得点はそれぞれ $ 1,\ 3,\ 0,\ 0 $ - $ (2,\ 1,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8) $：プレイヤーの得点はそれぞれ $ 0,\ 0,\ 0,\ 0 $ - $ (8,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 1) $：プレイヤーの得点はそれぞれ $ 8,\ 2,\ 0,\ 0 $ したがって、$ 2 $ ラウンド目でのそれぞれのプレイヤーの得点の期待値はそれぞれ $ 7/4,\ 11/4,\ 1/2,\ 5/8 $ となります。