← 返回题目列表

AtCoder · arc133_f

F. 随机转换

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

分数: 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