AT_s8pc_6_f Random Shuffles

新学期伊始，E869120 君想在新的班级中展开互动，于是他设计了一种卡片游戏。 - 共有 $N$ 张卡片，编号分别是 $1, 2, 3, \ldots, N$。 - 每张卡片被涂上一种颜色，颜色共有 $D$ 种，用数字 $0, 1, 2, \ldots, D-1$ 表示。 - 第 $i$ 张卡片的颜色是 $S_i\ (0 \leq S_i < D)$，卡片上写着编号 $i$。 这款游戏有 $D$ 名玩家参与，规则如下： 1. 首先，将编号为 $1, 2, 3, \ldots, k$ 的卡片依次叠起来，形成一个牌堆。 2. 然后，重复进行以下操作 $L$ 次： - 随机选择一个整数 $i$，$1 \le i \le k$，交换从上往下的第 $i$ 张卡片和第 $i+1$ 张卡片的位置。 3. 最后，将牌堆中的卡片按照玩家 $1, 2, 3, \ldots, D, 1, 2, 3,\ldots, D$ 的顺序逐一发给每位玩家。 4. 任何玩家的得分等于他手中涂有颜色 $(i-1)$ 的卡片上的数字之和。 特别注意，在步骤 2 中，“从上到下第 $k+1$ 张卡片”代表的是“从上到下第 1 张卡片”。 游戏共进行 $N \div D$ 轮。在第 $i$ 轮，游戏中的 $k = i \times D$。请计算每轮中每个玩家的得分期望值。 **由于输出数据可能很大，输出格式会有所不同，请参阅“输出格式”部分。**

输入通过标准输入给出，格式如下： > $N$ $D$ $L$ $S_{1}S_{2}S_{3}S_{4}\ldots S_{N}$ $S_1, S_2, \ldots, 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, \ldots, 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$ ### 样例解释 #### 样例 1 假设初始卡片排列为 $(1, 2, 3)$，进行 $L=1$ 次操作后，可能得到的排列有 $(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 在第 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$。 **本翻译由 AI 自动生成**