P12405 「CZOI-R3」星光闪耀

> 今夜星光闪闪 我爱你的心满满 ……

天空中有一个包含 $n$ 颗星星的星团。 小 K 认为天空中只有一个星团不够浪漫，因此她准备施展魔法。若在她施展魔法前第 $i$ 个星团包含 $a_i$ 颗星星，且 $a_i\ge2$；则施展魔法后天空中**分别**增加包含 $1\sim a_i-1$ 颗星星的星团（注意原本的星团会被保留）。 小 K 定义一个包含 $v$ 颗星星的星团的**闪耀度**为 $k^v$。求她施展 $m$ 次魔法后，天空中所有星团的**闪耀度**之和，对 $998244353$ 取模。 ------------ **【形式化题意】** 给定一个可重集 $S_0$，初始 $S_0$ 中只有一个数 $n$。 定义一次操作为：新建一个可重集 $S_1$，对于 $\forall1\le i\le|S_0|$，若 $S_{0,i}\ge 2$，则对于 $\forall1\le j\le S_{0,i}-1$，将 $j$ 加入 $S_1$。在这次操作的最后，将 $S_1$ 中所有元素加入 $S_0$。 求进行了 $m$ 次操作后的 $\sum_{i=1}^{|S_0|} k^{S_{0,i}}$，对 $998244353$ 取模。

无

无

**【样例解释】** 以下记 $L_i$ 表示包含 $i$ 颗星星的星团的个数，即 $S_{0,j}=i$ 的个数。 第 $1$ 组测试数据中： - 第一次施展魔法（进行操作）后 $L_1=1,L_2=1,L_3=1$。 - 第二次施展魔法（进行操作）后 $L_1=3,L_2=2,L_3=1$。 - 第三次施展魔法（进行操作）后 $L_1=6,L_2=3,L_3=1$。 - 第四次施展魔法（进行操作）后 $L_1=10,L_2=4,L_3=1$。 因此答案为 $10\times6^1+4\times6^2+1\times6^3=420$。 第 $2$ 组测试数据中： - 第一次施展魔法（进行操作）后 $\forall1\le i\le n,L_i=1$。 - 第二次施展魔法（进行操作）后 $\forall1\le i\le n,L_i=n-i+1$。 因此答案为 $\sum_{i=1}^n(n-i+1)5^i=610340$。 **【数据范围】** **本题采用捆绑测试**。 记 $\sum n,\sum m$ 分别为单个测试点内 $n,m$ 的和。 - Subtask #1（$5\text{ pts}$）：$k=0$。 - Subtask #2（$10\text{ pts}$）：$n\le5$ 且 $m\le5$。 - Subtask #3（$10\text{ pts}$）：$m\le3$。 - Subtask #4（$10\text{ pts}$）：$k=1$。 - Subtask #5（$10\text{ pts}$）：$n\le2\times10^2$ 且 $m\le2\times10^2$ 且单个测试点内的 $k$ 相等。 - Subtask #6（$10\text{ pts}$）：$n\le2\times10^3$ 且 $m\le2\times10^3$ 且单个测试点内的 $k$ 相等。 - Subtask #7（$15\text{ pts}$）：$\sum n\le2\times10^7$。 - Subtask #8（$15\text{ pts}$）：$\sum m\le2\times10^6$。 - Subtask #9（$15\text{ pts}$）：无特殊限制。 对于 $100\%$ 的数据，$1\le T\le5\times10^5$，$1\le n\le2\times10^6$，$1\le m\le2\times10^6$，$\sum m\le2\times10^7$，$0\le k\le998244352$。 **本题 IO 量较大，请采用较快的 IO 方式。**