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