AT_arc133_f.[ARC133F] Random Transition

给定一个整数 $N$。

すぬけくん将进行如下操作：

• 准备一个变量 $x$，并用 $0$ 到 $N$ 之间随机选取的整数进行初始化。对于每个 $0 \leq i \leq N$，$x=i$ 的初始化概率为 $A_i/10^9$。
• 接下来重复 $K$ 次如下操作：
  • 以概率 $x/N$ 将 $x$ 的值减 $1$，以概率 $1-x/N$ 将 $x$ 的值加 $1$。（注意，操作后 $x$ 的值始终保证在 $0$ 到 $N$ 之间）

对于每个 $i=0,1,\cdots,N$，请计算所有操作结束后 $x=i$ 的概率，并对 $998244353$ 取模。

概率 $\pmod{998244353}$ 的定义：可以证明，所求概率一定是有理数。此外，在本题的约束下，将其表示为最简分数 $\frac{P}{Q}$ 时，$Q \not\equiv 0 \pmod{998244353}$ 也成立。因此，存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353},\ 0 \leq R < 998244353$。请输出这个 $R$。

输入按以下格式从标准输入给出：

$N$ $K$ $A_0$ $A_1$ $\cdots$ $A_N$

对于每个 $i=0,1,\cdots,N$，输出所有操作结束后 $x=i$ 的概率，对 $998244353$ 取模。

限制条件

• $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$
• 输入的所有值均为整数

样例解释 1

最初必定初始化为 $x=1$。之后的操作中，以 $1/2$ 的概率将 $x$ 的值减 $1$，以 $1/2$ 的概率将 $x$ 的值加 $1$。最终 $x=0,1,2$ 的概率分别为 $1/2,0,1/2$。

由 ChatGPT 4.1 翻译