题目详情题解（0）讨论（0）提交记录（0）

AT_s8pc_6_f.Random Shuffles

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

新学期伊始，E869120 君想在新的班级中展开互动，于是他设计了一种卡片游戏。

  • 共有 NN 张卡片，编号分别是 1,2,3,…,N1, 2, 3, \ldots, N。
  • 每张卡片被涂上一种颜色，颜色共有 DD 种，用数字 0,1,2,…,D−10, 1, 2, \ldots, D-1 表示。
  • 第 ii 张卡片的颜色是 Si (0≤Si<D)S_i\ (0 \leq S_i < D)，卡片上写着编号 ii。

这款游戏有 DD 名玩家参与，规则如下：

  1. 首先，将编号为 1,2,3,…,k1, 2, 3, \ldots, k 的卡片依次叠起来，形成一个牌堆。
  2. 然后，重复进行以下操作 LL 次：
    • 随机选择一个整数 ii，1≤i≤k1 \le i \le k，交换从上往下的第 ii 张卡片和第 i+1i+1 张卡片的位置。
  3. 最后，将牌堆中的卡片按照玩家 1,2,3,…,D,1,2,3,…,D1, 2, 3, \ldots, D, 1, 2, 3,\ldots, D 的顺序逐一发给每位玩家。
  4. 任何玩家的得分等于他手中涂有颜色 (i−1)(i-1) 的卡片上的数字之和。

特别注意，在步骤 2 中，“从上到下第 k+1k+1 张卡片”代表的是“从上到下第 1 张卡片”。

游戏共进行 N÷DN \div D 轮。在第 ii 轮，游戏中的 k=i×Dk = i \times D。请计算每轮中每个玩家的得分期望值。

由于输出数据可能很大，输出格式会有所不同，请参阅“输出格式”部分。

输入格式

输入通过标准输入给出，格式如下：

NN DD LL S1S2S3S4…SNS_{1}S_{2}S_{3}S_{4}\ldots S_{N}

S1,S2,…,SNS_1, S_2, \ldots, S_N 是一个整体数字串。

输出格式

依次输出 DD 行。
第 ii 行应该输出玩家 ii 在 N÷DN \div D 轮游戏中得分期望值的总和。
答案的绝对误差或相对误差都不能超过 10−510^{-5}。

输入输出样例

  • 输入#1

    3 3 1
012

    输出#1

    0.333333333333
0.666666666667
1.000000000000

  • 输入#2

    8 4 1
01123310

    输出#2

    2.250000000000
4.500000000000
1.500000000000
0.625000000000

  • 输入#3

    20 4 15
10232310010022312313

    输出#3

    34.068777543023
27.854472795592
22.354635768263
28.066210471955

说明/提示

约束条件

  • DD 是 33 到 1010 之间的整数
  • NN 是 33 到 3,000,0003,000,000 之间的 DD 的倍数
  • LL 范围在 11 到 1,000,000,0001,000,000,000 之间
  • Si (1≤i≤N)S_i\ (1 \leq i \leq N) 是 0,1,2,…,D−10, 1, 2, \ldots, D-1 的一个数

子任务

这个问题被分为若干个子任务，每个子任务都需要满足其所有测试用例：

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

样例解释

样例 1

假设初始卡片排列为 (1,2,3)(1, 2, 3)，进行 L=1L=1 次操作后，可能得到的排列有 (1,3,2)(1, 3, 2), (2,1,3)(2, 1, 3), 和 (3,2,1)(3, 2, 1)，每种排列的出现概率均为 1/31/3。
对每种排列，玩家的得分为：

  • (1,3,2)(1, 3, 2)：玩家得分分别是 1,0,01, 0, 0
  • (2,1,3)(2, 1, 3)：玩家得分分别是 0,0,30, 0, 3
  • (3,2,1)(3, 2, 1)：玩家得分分别是 0,2,00, 2, 0

因此，玩家的期望得分分别为 1/3,2/3,11/3, 2/3, 1。

样例 2

在第 1 轮中，以下 4 种情况均等概率可能发生：

  • (1,2,4,3)(1, 2, 4, 3)：玩家得分分别是 1,2,4,01, 2, 4, 0
  • (1,3,2,4)(1, 3, 2, 4)：玩家得分分别是 1,3,0,01, 3, 0, 0
  • (2,1,3,4)(2, 1, 3, 4)：玩家得分分别是 0,0,0,00, 0, 0, 0
  • (4,2,3,1)(4, 2, 3, 1)：玩家得分分别是 0,2,0,00, 2, 0, 0

因此，第 1 轮时，各玩家的期望得分分别是 1/2,7/4,1,01/2, 7/4, 1, 0。

在第 2 轮中，以下 8 种情况均等概率可能发生：

  • (1,2,3,4,5,6,8,7)(1, 2, 3, 4, 5, 6, 8, 7)：玩家��分分别是 1,2,0,01, 2, 0, 0
  • (1,2,3,4,5,7,6,8)(1, 2, 3, 4, 5, 7, 6, 8)：玩家得分分别是 1,9,0,01, 9, 0, 0
  • (1,2,3,4,6,5,7,8)(1, 2, 3, 4, 6, 5, 7, 8)：玩家得分分别是 1,2,0,01, 2, 0, 0
  • (1,2,3,5,4,6,7,8)(1, 2, 3, 5, 4, 6, 7, 8)：玩家得分分别是 1,2,0,51, 2, 0, 5
  • (1,2,4,3,5,6,7,8)(1, 2, 4, 3, 5, 6, 7, 8)：玩家得分分别是 1,2,4,01, 2, 4, 0
  • (1,3,2,4,5,6,7,8)(1, 3, 2, 4, 5, 6, 7, 8)：玩家得分分别是 1,3,0,01, 3, 0, 0
  • (2,1,3,4,5,6,7,8)(2, 1, 3, 4, 5, 6, 7, 8)：玩家得分分别是 0,0,0,00, 0, 0, 0
  • (8,2,3,4,5,6,7,1)(8, 2, 3, 4, 5, 6, 7, 1)：玩家得分分别是 8,2,0,08, 2, 0, 0

因此，第 2 轮时，各玩家的期望得分分别是 7/4,11/4,1/2,5/87/4, 11/4, 1/2, 5/8。

本翻译由 AI 自动生成

输入解题思路，AI测评打分。不知道怎么写?

首页