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 翻译