C - Addictive Addition
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
長さ 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|\) かつ \((S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})\)。
-
ある整数 \(1 \le i \le \min\{|S|,|T|\}\) が存在して、下記の 2 つがともに成り立つ。
- \((S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})\)
- \(S_i\) が \(T_i\) より（数として）小さい。
制約
- 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 以下
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
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
4 2 1 3 2 3 3 2 4 3 1 2 5 7 100 23 38 19 78 97 12 66621153 962738384 596076187 241253251 294255618 160313007 362465084 613302073 172378047 202387723 783794852 575378463 266956797 649540193
出力例 1
2 1 0 10 0 0 10 166591803 201113277 0 215366213 869870626 294965523 742219241 0 0 0 0 357811811 0 0 797772154 0 0 0 896363579
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 となります。