← 返回题目列表

AtCoder · npcapc_2024_d

D. 两盒

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

配点 : 100 点

問題文

长度 N 的非负整数序列 给出 A=(A_1,A_2,\dots,A_N) 和 Q 查询。i 第二次查询的内容如下。

  • A_{x_i} 是 y_i 然后 查找以下有关 A 问题的答案。

白盒和黑盒 编号为 1 我决定将所有值添加到 M 有 M 球。一开始,所有的球都在一个白色的盒子里。

在这里,您可以执行以下操作: 重复 N 次。 选择

  • 1 \le x \le M 的整数 x 。球 将 x 从它所在的盒子移动到另一个盒子。

i 第一次运算后,黑匣子里所有球的编号都是 必须小于或等于 A_i 。可能的操作序列数为 998244353 后求余数。

请按顺序处理查询。

制約

  • 1 \le N,Q \le \textcolor{red}{3 \times 10^4}
  • 1 \le M \le 15
  • 1 \le x_i \le N
  • 1 \le A_i,y_i \le M

部分点

这个问题有多个部分点。 如果正确答案是满足

  • N \le 2000,M \le 10,Q = 1 的数据集 如果满足 10 点。
  • Q = 1 的数据集的答案是正确的,则附加 10 点。

入力

输入将以以下形式从标准输入给出。

N M Q
A_1 A_2 \dots A_N
x_1 y_1
x_2 y_2
\vdots
x_Q y_Q

出力

Q 行。 输出i 在线 i 输出查询的答案。 对于第


入力例 1

3 3 2
1 3 1
3 2
1 3

出力例 1

5
14

1 个查询,A=(1,3,2) 。此时,例如可以考虑以下操作顺序。

  • x = 1 。球从白盒子到黑盒子 1 移动。黑盒子里的球 包括 1 。
  • x = 3 。球从白盒子到黑盒子 3 移动。黑盒子里的球 包括 1,3 。
  • x = 3 。球从黑盒子到白盒子 1 移动。黑盒子里的球 包括 1 。

除了这个 x 的可能列是 (1,1,1),(1,1,2),(1,2,1),(1,2,2) 的 4 没错。因此,可能的操作顺序为 5 没错。


入力例 2

6 8 1
3 8 7 7 1 6
1 4

出力例 2

2100

入力例 3

12 10 8
1 3 2 6 3 6 7 7 5 5 4 7
12 4
7 10
4 2
9 8
9 9
8 3
4 9
10 2

出力例 3

2741280
3007680
1503840
1916160
1972800
728640
1821600
621440