F - Random Shuffles Editorial /

Time Limit: 1 sec / Memory Limit: 976 MB

配点：1000 点

問題文

新学期も始まり、新しいクラスで交流を行いたいと思った E869120 君は、次のようなカードゲームを考えました。

  • N 枚のカードがあり、1, 2, 3,..., N と番号付けられています。
  • カードは D 種類の色のいずれかで塗られており、色は 0, 1, 2,..., D-1 のいずれかの数で表されます。
  • カード i は色 S_i \ (0 \leq S_i < D) で塗られており、i という数が書かれています。

このカードを用いて、D 人でカードゲームを行います。ルールは以下の通りです：

  1. まず、番号 1, 2, 3, ..., k のカードを重ねて山にします。番号 i のカードが上から i 番目に来るようにします。
  2. 次 (3.) の操作を L 回繰り返します。
  3. 1 以上 k 以下のランダムな整数 i を選び、上から i 枚目のカードと上から i+1 枚目のカードの位置を入れ替えます。
  4. 最後、カードの山の上から順に、プレイヤー 1, 2, 3,..., D, 1, 2, 3,..., D, 1, 2,... という順番で 1 枚ずつ配っていきます。
  5. プレイヤー i の得点は、そのプレイヤーが持っているカードのうち色 (i-1) が塗られたものに書かれた数の合計です。

ただし、3. では「上から k+1 枚目のカード」は「上から 1 枚目のカード」を指すことにします。

このゲームは N \div D ラウンドにわたって行われます。i 回目のラウンドは、k = i \times D でゲームを行います。
そのとき、それぞれのラウンドに対して各プレイヤーの得点の期待値を求めてください。

ただし、出力サイズの都合上、出力の形式が通常と違うので、「出力」の項をお読みください。

制約

  • 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

入力

入力は以下の形式で標準入力から与えられます。
ただし、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} 未満であれば、正解と見做されます。

入力例 1

3 3 1
012

出力例 1

0.333333333333
0.666666666667
1.000000000000

カードの並びを最初 (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 になります。

入力例 2

8 4 1
01123310

出力例 2

2.250000000000
4.500000000000
1.500000000000
0.625000000000

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 となります。

入力例 3

20 4 15
10232310010022312313

出力例 3

34.068777543023
27.854472795592
22.354635768263
28.066210471955

Max Score：1000 points

Problem Statment

In Japan, school starts from April. Since E869120 wanted to play with other classmates, he came up with the following card game.

  • There are N cards, which is numbered 1, 2, 3, ..., N.
  • There are D species of colors in cards, which is numbered 0, 1, 2, ..., D-1.
  • Card i is colored with color S_i \ (0 \leq S_i < D), and the number i is written on it.

The card game will be played by D players, with using the cards. The rule is following:

  1. First, make a pile with card 1, 2, 3, ..., k. Card i should be located at i-th from topmost.
  2. Repeat next operation (3.), K times.
  3. Choose the random integer i between 1 and k (inclusive) with equal probability, and swap the i-th topmost card and (i+1)-th topmost card currently.
  4. Distribute the cards to players. More precisely, player 1, 2, 3,..., D, 1, 2, 3, ..., D, 1, 2, 3, ..., D, 1, 2,... will get the 1, 2, 3, 4, 5, 6,..., k-th topmost card, respectively.
  5. The score of player i is the total number written on cards himself/herself have with color (i-1).

Please note that, for operation 3., "(k+1)-th topmost cards" means "1-st topmost cards$ instead.

This game consists of N \div D rounds. In the i-th round, the game will be played at k = i \times D.
For each round, calculate the expected value of score for each players.

Please note that the format of output is different, due to the size matter of output. See "Output" section for details.

Constraints

  • D is between 3 and 10 (inclusive).
  • N is between 3 and 3 \ 000 \ 000 (inclusive).
  • K is between 1 and 1 \ 000 \ 000 \ 000 (inclusive).
  • S_i \ (1 \leq i \leq N) is either of 0, 1, 2, ..., D-1.

Subtasks / Scoring

This problem is separated several two subtasks, and you will get score of the subtask if your program prints the correct answer for all testcases for the subtask prepared.
The score for a program is the sum of score of subtasks of correct answer.

  1. (50 points)：N \leq 10, D \leq 4, K = 1
  2. (70 points)：N \leq 10, D \leq 4, K \leq 5
  3. (80 points)：N \leq 50, D \leq 4, K \leq 300
  4. (100 points)：N \leq 3 \ 000, D \leq 4, K \leq 300
  5. (210 points)：N \leq 3 \ 000, D \leq 4
  6. (130 points)：N \leq 50 \ 000, D \leq 4
  7. (40 points)：N \leq 150 \ 000, D \leq 6
  8. (40 points)：N \leq 300 \ 000, D \leq 8
  9. (40 points)：N \leq 500 \ 000, D \leq 10
  10. (40 points)：N \leq 800 \ 000, D \leq 10
  11. (200 points)：N \leq 3 \ 000 \ 000, D \leq 10

入力

The input will be given from the Standard Input, in the following format.
Note that, for S_1, S_2, ..., S_N, it will be given as a string concatenated them (all S_i are one-digit numbers). 

N D L
S_{1}S_{2}S_{3}S_{4} ... S_{N}

Output

Print in D lines. In i-th line, print the sum of expected score of all N \div D rounds, for player i.
If the relative or absolute error is 10^{-5} or less, your program is regarded as correct.

Sample Input 1

3 3 1
012

Sample Output 1

0.333333333333
0.666666666667
1.000000000000

Let the initial arrangement of cards (1, 2, 3). After K=1 time "operation 3" in problem statement, the arrangement of cards, (1, 3, 2), (2, 1, 3), (3, 2, 1) will be equally probable with probability 1/3.

For each possibility, the scores of players will be following:

  • (1, 3, 2)：Players' score will be 1, 0, 0
  • (2, 1, 3)：Players' score will be 0, 0, 3
  • (3, 2, 1)：Players' score will be 0, 2, 0

Thus, the expected value of players' score will be 1/3, 2/3, 1.

Sample Input 2

8 4 1
01123310

Sample Output 2

2.250000000000
4.500000000000
1.500000000000
0.625000000000

In 1-st round, the following 4 scenarios are equally possible.

  • (1, 2, 4, 3)：Players' score will be 1, 2, 4, 0
  • (1, 3, 2, 4)：Players' score will be 1, 3, 0, 0
  • (2, 1, 3, 4)：Players' score will be 0, 0, 0, 0
  • (4, 2, 3, 1)：Players' score will be 0, 2, 0, 0

Hence, the expected score for each players in 1-st round, will be 1/2, 7/4, 1, 0.

In 2-nd round, the following 8 scenarios are equally possible.

  • (1, 2, 3, 4, 5, 6, 8, 7)：Players' score will be 1, 2, 0, 0
  • (1, 2, 3, 4, 5, 7, 6, 8)：Players' score will be 1, 9, 0, 0
  • (1, 2, 3, 4, 6, 5, 7, 8)：Players' score will be 1, 2, 0, 0
  • (1, 2, 3, 5, 4, 6, 7, 8)：Players' score will be 1, 2, 0, 5
  • (1, 2, 4, 3, 5, 6, 7, 8)：Players' score will be 1, 2, 4, 0
  • (1, 3, 2, 4, 5, 6, 7, 8)：Players' score will be 1, 3, 0, 0
  • (2, 1, 3, 4, 5, 6, 7, 8)：Players' score will be 0, 0, 0, 0
  • (8, 2, 3, 4, 5, 6, 7, 1)：Players' score will be 8, 2, 0, 0

Hence, the expected score for each players in 2-nd round, will be 7/4, 11/4, 1/2, 5/8.

Sample Input 3

20 4 15
10232310010022312313

Sample Output 3

34.068777543023
27.854472795592
22.354635768263
28.066210471955