P11687 [JOIGST 2024] 年轮蛋糕 2 / バームクーヘン 2

译自 [日本情報オリンピック 第4回女性部門 (JOIG 2023/2024) 春季トレーニング](https://www2.ioi-jp.org/joig-camp/2024/2024-sp-tasks/) R1T2。 图：年轮蛋糕。バームクーヘン = baumkuchen，即树木（德语 baum）+ 蛋糕（德语 kuchen）。图源百度百科。 

葵计划举办一场派对，共有 $K$ 人参加，编号 $1\sim K$。 众人将分享一个**环形的**年轮蛋糕。蛋糕的圆周上均匀刻有 $K \times L$ 个切缝，蛋糕只能沿切缝分割。 将切缝按顺时针编号 $1\sim K\times L$，切缝 $i$ 和切缝 $\left(i\bmod KL\right) +1$ 之间的区域叫做第 $i$ 个部分。 分割规则如下： 1. 选择 $K$ 个切缝切割，将蛋糕分为 $K$ 块，每个块包含恰好 $L$ 个**连续的**部分。 2. 把 $K$ 块蛋糕分给 $K$ 个人，要求每个人都恰好分到一块蛋糕。 现在有 $Q$ 条限制，第 $j$ 条限制要求第 $X_j$ 个部分必须被分配给第 $Y_j$ 个人。保证每个部分 $X_j$ 只会在限制中出现一次。 对于 $i=1,2,\cdots,Q$，求出有多少种切蛋糕和分蛋糕的方案满足前 $i$ 条限制，对给定的素数 $P$ 取模。 两个方案不同，当且仅当存在一个人，他在这两个方案中拿到了不同的蛋糕块。

如下所示： > $K$ $L$\ > $P$\ > $Q$ > $X_1$ $Y_1$\ > $X_2$ $Y_2$\ > $\vdots$\ > $X_Q$ $Y_Q$

输出 $Q$ 行，每行一个整数，表示满足前 $i$ 条限制的方案数量对 $P$ 取模后的结果。

### 样例解释 #### 样例 $1$ 解释 $i=1$ 时，要求将包含第 $1$ 个部分的块分给第 $2$ 个人，有 $4$ 个方案。举例： 1. 沿切缝 $1$、$3$、$5$ 切割蛋糕； 2. 分配方式： - 第 $1$ 个人：第 $3,4$ 个部分； - 第 $2$ 个人：第 $1,2$ 个部分； - 第 $3$ 个人：第 $5,6$ 个部分。 $i=2$ 时，在 $i=1$ 的基础上额外要求将包含第 $6$ 个部分的块分配给第 $2$ 个人，有 $2$ 个方案。举例： 1. 沿切缝 $2$、$4$、$6$ 切割蛋糕； 2. 分配方式： - 第 $1$ 个人：第 $4,5$ 个部分； - 第 $2$ 个人：第 $6,1$ 个部分； - 第 $3$ 个人：第 $2,3$ 个部分。 该样例满足所有子任务的限制。 #### 样例 $2$ 解释 该样例满足所有子任务的限制。 #### 样例 $3$ 解释 该样例满足子任务 $2\sim 6$ 的限制。 ### 数据范围 - $2\le K\le 2\times 10^5$； - $1\le L\le 2\times 10^5$； - $10^8\lt P\lt 10^9$； - $P$ 是素数； - $1\le Q\le 2\times 10^5$； - $\forall 1\le j\le Q$，$1\le X_j\le KL$； - $\forall 1\le j\lt k\le Q$，$X_j\neq X_k$； - $\forall 1\le j\le Q$，$1\le Y_j\le k$； - 输入的值全部是整数。 ### 子任务 1. （13pts）$K\le 8$，$L\le 10$，$Q\le 10$。 2. （14pts）$K\le 100$，$L\le 100$，$Q\le 100$。 3. （18pts）$K\le 400$，$L\le 400$，$Q\le 400$。 4. （17pts）$K\le 2\, 500$，$L\le 2\, 500$，$Q\le 2\, 500$； 5. （28pts）$K\le 40$； 6. （10pts）无额外限制。 翻译来自 DeepSeek-R1 并经过人工微调。