#P4204. 取球游戏

    ID: 3419 传统题 1000ms 256MiB 尝试: 214 已通过: 112 难度: 6 上传者: 标签>难度分类提高概率与期望期望线性性指示变量多项式与生成函数卷积转化数论快速幂CF2000

取球游戏

取球游戏

题目描述

有 MM 个球,一开始每个球均有一个初始标号,标号范围为 1∼N1\sim N 且为整数,标号为 ii 的球有 aia_i 个,并保证 ∑i=1Nai=M\sum_{i=1}^N a_i = M。

每次操作等概率取出一个球(即取出每个球的概率均为 1M\frac{1}{M}),若这个球标号为 k(k<N)k(k < N),则将它重新标号为 k+1k + 1;若这个球标号为 NN,则将其重标号为 11。(每次重新标号后,都把球放回,球的总数始终为 MM)

现在你需要求出,经过 KK 次这样的操作后,每个标号的球的期望个数。

输入格式

第一行三个正整数 N,M,KN,M,K,分别为标号种数、球的个数和操作次数。

第 22 行包含 NN 个非负整数 aia_i,表示初始标号为 ii 的球有 aia_i 个。

输出格式

包含 NN 行,第 ii 行为标号为 ii 的球的期望个数,四舍五入保留 33 位小数。

样例 #1

样例输入 #1

2 3 2
3 0

样例输出 #1

1.667
1.333

样例说明

第一次操作后,由于标号为 22 的球的个数为 00,所以必然是一个标号为 11 的球变为标号为 22 的球。所以有 22 个标号为 11 的球,有 11 个标号为 22 的球。

第二次操作后,有 13\frac{1}{3} 的概率标号为 22 的球变为标号为 11 的球(此时标号为 11 的球有 33 个),有 23\frac{2}{3} 的概率标号为 11 的球变为标号为 22 的球(此时标号为 11 的球有 11 个),所以标号为 11 的球的期望个数为 $\frac{1}{3}\times 3+\frac{2}{3}\times 1 = \frac{5}{3}$。同理可求出标号为 22 的球期望个数为 43\frac{4}{3}。

数据规模与约定

对于 100%100\% 的数据:N≤103N \le 10^3,M≤108M \le 10^8,K≤2147483647K \le 2147483647。