配点 : 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