AT_oupc2023_day1_o.Special Matrix

本题中使用以下数学表示法：

• $M_{i,j}$：表示矩阵 $M$ 的第 $i$ 行第 $j$ 列的元素。
• $\text{GCD}(x,y)$：表示 $x$ 与 $y$ 的最大公约数。

我们将满足下列条件的 $N$ 行 $N$ 列的非负整数矩阵 $M$ 称为“特殊矩阵”：

• 对于 $1 \leq i,j \leq N$，当 $i < j$ 时，有 $M_{i,j}=0$，当 $i \geq j$ 时，有 $M_{i,j}>0$。
• $M_{1,1}=a$。
• 存在一个长度为 $N$ 的等比数列 $X=(X_1,X_2,\dots,X_N)$，使得对任意 $1 \leq j \leq i \leq N$，有 $(M^P)_{i,j}=M_{i,j} \times X_{i-j+1}$。
• 对于 $1 \leq k \leq K$，有 $\text{GCD}(M_{A_k,B_k},C_k)=D_k$。

现在有 $Q$ 个询问。对于第 $q$ 个询问，请对于所有“特殊矩阵” $M$，输出 $M_{E_q,F_q}$ 的最小值对 $998244353$ 取余的结果。如果不存在满足条件的“特殊矩阵”，则输出 -1。

输入按如下格式从标准输入读入：

$N$　$P$　$a$　$K$　$A_1$　$B_1$　$C_1$　$D_1$　$A_2$　$B_2$　$C_2$　$D_2$　$\vdots$　$A_K$　$B_K$　$C_K$　$D_K$　$Q$　$E_1$　$F_1$　$E_2$　$F_2$　$\vdots$　$E_Q$　$F_Q$

请输出 $Q$ 行。第 $q$ 行输出对应第 $q$ 个询问的答案。

子任务

1.（1 分）$N \leq 30$
2.（99 分）无其他额外限制

样例说明 1

对于第 1 个查询，例如 $M=\begin{pmatrix} 2 & 0 \\ 3 & 2 \end{pmatrix}$ 就是 $M_{2,2}$ 最小的“特殊矩阵”。

该测试用例满足子任务 1 的约束。

样例说明 2

不存在满足条件的“特殊矩阵”。

该测试用例满足子任务 1 的约束。

数据范围

• $1 \leq N \leq 1\,000$
• $2 \leq P \leq 10^{9}$
• $1 \leq a \leq 10^{9}$
• $0 \leq K \leq \min(1\,000,\frac{N(N-1)}{2})$
• $1 \leq B_k < A_k \leq N$
• $(A_1,B_1),(A_2,B_2),\dots,(A_K,B_K)$ 均不相同
• $1 \leq D_k \leq C_k \leq 10^{9}$
• $C_k$ 能被 $D_k$ 整除
• $1 \leq Q \leq 70$
• $1 \leq F_q \leq E_q \leq N$
• 所有输入均为整数。

由 ChatGPT 5 翻译