← 返回题目列表

AtCoder · KeioPC2025_c

C. 上瘾的添加

中文机器翻译题面 查看原题

配点 : 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\)的长度。

  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|\}\) 使得以下 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 。 对于