最高分数:1000 点
问题陈述
在日本,学校从四月开始。由于E869120想和其他同学一起玩,所以他想出了以下纸牌游戏。
- 有 N 卡片,已编号 1, 2, 3, ..., N.
- 有 D 卡片中的颜色种类,已编号 0, 1, 2, ..., D-1.
- 卡 i 是用颜色着色的 S_i \ (0 \leq S_i < D),以及数量 上面写着 i 。
纸牌游戏将由 D 玩家,使用卡片。规则如下:
- 首先,用卡片堆成一堆 1, 2, 3, ..., k。卡 i 应位于 i- 从最上面算起。
- 重复下一个操作(3.), K 次。
- 选择随机整数 i 之间 1 和 k (含)等概率,交换 i- 第一张最上面的牌和 (i+1)当前最上面的卡。
- 将卡片分发给玩家。更准确地说,玩家 1, 2, 3,..., D, 1, 2, 3, ..., D, 1, 2, 3, ..., D, 1, 2,... 将得到 1, 2, 3, 4, 5, 6,..., k- 第一张最上面的牌。
- 玩家得分 i 是他/她自己拥有的彩色卡片上写的总数 (i-1).
请注意,对于操作 3.,“(k+1)- 第一张最上面的牌“表示”1-st 最上面的卡片 $ 代替。
这个游戏包括 N \div D 回合。在 i第轮,比赛将于 k = i \times D.
对于每一轮,计算每个玩家的期望得分值。
请注意,由于输出的大小问题,输出的格式有所不同。有关详细信息,请参阅“输出”部分。
约束
- D 介于 3 和 10 (含)。
- N 介于 3 和 3 \ 000 \ 000 (含)。
- K 介于 1 和 1 \ 000 \ 000 \ 000 (含)。
- S_i \ (1 \leq i \leq N) 是其中之一 0, 1, 2, ..., D-1.
子任务/评分
这个问题被分成几个子任务,如果你的程序打印出准备好的子任务的所有测试用例的正确答案,你将获得子任务的分数。
程序的分数是正确答案的子任务分数的总和。
- (50分):N \leq 10, D \leq 4, K = 1
- (70分):N \leq 10, D \leq 4, K \leq 5
- (80分):N \leq 50, D \leq 4, K \leq 300
- (100分):N \leq 3 \ 000, D \leq 4, K \leq 300
- (210分):N \leq 3 \ 000, D \leq 4
- (130分):N \leq 50 \ 000, D \leq 4
- (40分):N \leq 150 \ 000, D \leq 6
- (40分):N \leq 300 \ 000, D \leq 8
- (40分):N \leq 500 \ 000, D \leq 10
- (40分):N \leq 800 \ 000, D \leq 10
- (200分):N \leq 3 \ 000 \ 000, D \leq 10
入力
输入将从标准输入给出,格式如下。
请注意,对于
您打印的 S_1, S_2, ..., S_N,它将作为连接它们的字符串给出(所有 S_i 是一位数)。
N D L
S_{1}S_{2}S_{3}S_{4} ... S_{N}
输出
打印 D 行。在 i第行,打印 总和 全部的预期分数 N \div D 轮,针对玩家 i.
如果相对或绝对误差为 10^{-5} 或更少,你的程序被认为是正确的。
示例输入 1
3 3 1 012
示例输出 1
0.333333333333 0.666666666667 1.000000000000
让卡片初始排列 (1, 2, 3).之后 K=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
In 1-st 轮,以下 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-st 轮,将是 1/2, 7/4, 1, 0.
In 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