AT_npcapc_2024_d Two Box

给定一个长度为 $N$ 的非负整数序列 $A=(A_1,A_2,\dots,A_N)$，以及 $Q$ 个查询。第 $i$ 个查询内容如下： - 将 $A_{x_i}$ 修改为 $y_i$，然后对于此时的 $A$，解决以下问题： > 有一个白色盒子和一个黑色盒子，以及编号从 $1$ 到 $M$ 的 $M$ 个球。一开始，所有球都在白色盒子中。 > > 你需要进行 $N$ 次操作，每次操作如下： > > - 选择一个整数 $x$，满足 $1 \le x \le M$。将编号为 $x$ 的球从当前所在的盒子移到另一个盒子。 > > 第 $i$ 次操作结束后，黑色盒子中所有球的编号都必须不大于 $A_i$。请你求出所有可能的操作序列的数量，对 $998244353$ 取模。 请依次输出每个查询的答案。

输入以如下格式从标准输入读入： > $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$ 个查询的答案。

### 部分分 本题设置了多个部分分。 - 满足 $N \le 2000,M \le 10,Q = 1$ 的数据集可获得 $10$ 分。 - 满足 $Q = 1$ 的数据集可再得 $10$ 分。 ### 样例说明 1 在第 $1$ 次查询时，$A=(1,3,2)$。此时，设可能的操作序列如下： - 选择 $x=1$。将编号为 $1$ 的球从白盒子移到黑盒子。此时黑盒子里的是球 $1$。 - 选择 $x=3$。将编号为 $3$ 的球从白盒子移到黑盒子。此时黑盒子里是 $1,3$。 - 选择 $x=3$。将 $1$ 号球从黑盒子移回白盒子。此时黑盒子中仅有球 $3$。 此外还有 $x$ 的操作序列 $(1,1,1),(1,1,2),(1,2,1),(1,2,2)$ 共 $4$ 种。因此，一共有 $5$ 种可能的操作序列。 ### 数据范围 - $1 \le N,Q \le 3 \times 10^4$ - $1 \le M \le 15$ - $1 \le x_i \le N$ - $1 \le A_i,y_i \le M$ 由 ChatGPT 5 翻译