← 返回题目列表

AtCoder · s8pc_6_f

F. 随机洗牌

中文机器翻译题面 查看原题

最高分数: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.), K 次。
  3. 选择随机整数 i 之间 1 和 k (含)等概率,交换 i- 第一张最上面的牌和 (i+1)当前最上面的卡。
  4. 将卡片分发给玩家。更准确地说,玩家 1, 2, 3,..., D, 1, 2, 3, ..., D, 1, 2, 3, ..., D, 1, 2,... 将得到 1, 2, 3, 4, 5, 6,..., k- 第一张最上面的牌。
  5. 玩家得分 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.

子任务/评分

这个问题被分成几个子任务,如果你的程序打印出准备好的子任务的所有测试用例的正确答案,你将获得子任务的分数。
程序的分数是正确答案的子任务分数的总和。

  1. (50分):N \leq 10, D \leq 4, K = 1
  2. (70分):N \leq 10, D \leq 4, K \leq 5
  3. (80分):N \leq 50, D \leq 4, K \leq 300
  4. (100分):N \leq 3 \ 000, D \leq 4, K \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,它将作为连接它们的字符串给出(所有 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