AT_KeioPC2025_c Addictive Addition

给定一个长度为 $N$ 的正整数列 $A=(A_1,A_2,\dots,A_N)$。对于一个整数列 $X=(X_1,X_2,\dots,X_l)$，用如下方式定义 $f(X)$： - 对于 $0 \le i \le N$，定义正整数列 $C^{(i)}$ 为 $(A_1,A_2,\dots,A_i,X_1,X_2,\dots,X_l,A_{i+1},A_{i+2},\dots,A_N,\textcolor{red}{\boldsymbol{i}})$。在这 $N+1$ 个数列中，选择字典序最小的那一个（可以证明是唯一的），记为 $C^{(k)}$，则 $f(X) = k$。 请对于 $i=0,1,\dots,N$，解决如下问题： - 求所有长度在 $1$ 到 $M$ 之间且每个元素在 $1$ 到 $K$ 之间的正整数列 $B$ 中，满足 $f(B)=i$ 的序列个数，并对 $998244353$ 取模。 给定 $T$ 个测试用例，请分别求解。 什么是数列的字典序？假设 $S = (S_1,S_2,\ldots,S_{|S|})$，$T = (T_1,T_2,\ldots,T_{|T|})$。若满足下列 1. 或 2. 中之一，则称 $S$ **字典序小于** $T$。其中 $|S|,|T|$ 表示 $S,T$ 的长度。 1. $|S| < |T|$ 且 $(S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})$。 2. 存在整数 $1 \le i \le \min\{|S|,|T|\}$，使得以下两点都满足： - $(S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})$ - $S_i$ 比 $T_i$ （按数值）小。

输入通过标准输入给出，格式如下： > $T$ $\mathrm{case}_1$ $\vdots$ $\mathrm{case}_T$ 每个测试用例输入格式如下： > $N$ $M$ $K$ $A_1\ A_2\ \dots\ A_N$

输出 $T$ 行。第 $t$ 行请输出对于 $\mathrm{case}_t$，$i=0,1,\dots,N$ 的答案，按顺序用空格分隔。

### 样例解释 1 对于第 $1$ 个测试用例，枚举所有长度为 $1$，元素在 $1$ 到 $3$ 之间的正整数列 $B$，可以得到 $C^{(i)}$ 如下： - $B=(1)$ 时，$C^{(0)}=(1,2,3,0),C^{(1)}=(2,1,3,1),C^{(2)}=(2,3,1,2)$，因此 $f(B)=0$。 - $B=(2)$ 时，$C^{(0)}=(2,2,3,0),C^{(1)}=(2,2,3,1),C^{(2)}=(2,3,2,2)$，因此 $f(B)=0$。 - $B=(3)$ 时，$C^{(0)}=(3,2,3,0),C^{(1)}=(2,3,3,1),C^{(2)}=(2,3,3,2)$，因此 $f(B)=1$。 所以对于 $i=0,1,2$ 的答案分别为 $2,1,0$。 ### 数据范围 - $1 \le T \le 5 \times 10^5$ - $1 \le N \le 5 \times 10^5$ - $1 \le M \le 10^9$ - $1 \le K \le 10^9$ - $1 \le A_i \le K$ - 所有测试用例的 $N$ 之和不超过 $5 \times 10^5$ - 所有输入均为整数。 由 ChatGPT 5 翻译