分数: 1100 点
问题陈述
给定的是一个整数 N.
Snuke 将执行以下过程。
- 让 x 是一个变量,并用之间的随机整数初始化它 0 和 N (含)。对于每个 0 \leq i \leq N, x=i 被概率选择 A_i/10^9.
- 重复以下操作 K 次。
- 有概率 x/N,减少值 x by 1;有概率 1-x/N,增加 1。 (这里,请注意 x 仍将在 0 和 N 操作后。)
对于每个 i=0,1,\cdots,N,求概率,模 998244353,即 x=i 手术后。
概率模的定义 998244353
可以证明,求的概率总是有理数。另外,在这个问题的约束下,当将它们中的每一个表示为不可约分数时 \frac{P}{Q},可以证明 Q \neq 0 \pmod{998244353}。因此,唯一存在一个整数 R 这样 R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353。用这个回答 R.
约束
- 1 \leq N \leq 100000
- 0 \leq A_i
- \sum_{0 \leq i \leq N}A_i = 10^9
- 1 \leq K \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K A_0 A_1 \cdots A_N
输出
对于每个 i=0,1,\cdots,N,打印概率,模 998244353,即 x=i 手术后。
示例输入 1
2 1 0 1000000000 0
示例输出 1
499122177 0 499122177
首先, x 始终初始化为 x=1。 在后续的操作中,值 x 减少 1 有概率 1/2 并增加了 1 有概率 1/2。 最终,我们将拥有 x=0,1,2 的概率 1/2,0,1/2。
示例输入 2
4 2 200000000 200000000 200000000 200000000 200000000
示例输出 2
723727156 598946612 349385524 598946612 723727156
示例输入 3
10 100 21265166 263511538 35931763 26849698 108140810 134702248 36774526 147099145 58335759 4118743 163270604
示例输出 3
505314898 24510700 872096939 107940764 808162829 831195162 314651262 535843032 665830283 627881537 696038713