题意

构造一个 \(N\) 行 \(N\) 列的矩阵 \(X\)，需要满足下列条件（把 \(X\) 的第 \(i\) 行第 \(j\) 列的元素记作 \(x_{i,j}\)）：

• \(x_{i,j} \in \set{0, 1, 2}\)。
• 对于每个 \(i = 1, 2, \dots, Q\)，下述条件成立。
  • 令 \(P = \prod_{a_i \le j \le b_i} \prod_{c_i \le k \le d_i} x_{j,k}\)。\(P\) 模 \(3\) 和 \(e_i\) 同余。

限制

• \(1 \le N, Q \le 2000\)
• \(1 \le a_i \le b_i \le N\)
• \(1 \le c_i \le d_i \le N\)
• \(e_i \in \set{0, 1, 2}\)

分析

Quick observations：

• 每个乘积模 \(3\) 不等于 \(0\) 的矩形内都不能有 \(0\)。
• 每个乘积模 \(3\) 等于 \(0\) 的矩形内都至少有一个 \(0\)。
• \((2 \times 2) \bmod 3 = 1\)。每个 \(2\) 型区域里要有奇数个 \(2\)，每个 \(1\) 型区域里要有偶数个 \(2\)。

若某个 \(0\) 型区域，里面每个元素都被 \(1\) 型或 \(2\) 型条件覆盖，则无解。

如何判断是否一个 \(0\) 型区域里的每个元素都被 \(1\) 型或 \(2\) 型条件所覆盖？

• 用差分的技巧算出每个元素被 \(1\) 型或 \(2\) 型条件覆盖的总次数。
• 构造一个 \(N\) 行 \(N\) 列的矩阵 \(Z\)（行、列从 \(1\) 到 \(N\) 编号）：
  • 若 \(x_{i,j}\) 未被 \(1\) 型或 \(2\) 型条件覆盖，则 \(Z_{i,j} = 1\)，否则 \(Z_{i,j} = 0\)。
• 求 \(Z\) 的二维前缀和。
• 对每个 \(0\) 型区域，求 \(Z\) 的子矩阵和，看它是否大于 \(0\)。

列方程组求解。令 \(p_{i, j}\) 为子矩阵 \(X_{1..i,1..j}\) 里 \(2\) 的个数的奇偶性。 对每个 \(e_i\) 不等于 \(0\) 的条件，列出一个方程

\[ \color{blue} p_{b_i, d_i} + p_{a_i - 1, d_i} + p_{b_i, c_i - 1} + p_{a_i - 1, c_i - 1} = e'_i \]

• 若 \(e_i = 2\)，则 \(\color{blue} e'_i = 1\)，若 \(e_i = 1\)，则 \(\color{blue} e'_i = 0\)。
• 此方程是 \(\mathbb{F}_2\) 意义下的。
• 为了区别，此后，\(\mathbb{F}_2\) 意义下的东西都用\(\color{blue}\text{蓝色}\)写出。

这样得到的方程组里至多有 \(Q\) 个方程、\(4Q\) 个变量。

• 若此方程组无解，则不存在满足条件的矩阵 \(X\)。
• 否则一定存在满足条件的矩阵 \(X\)。

对于方程组的一组解 \(\color{blue} p\)，我们可以构造一个 \((N+1)\) 行 \((N+1)\) 列的二维前缀和矩阵 \(\color{blue} S\)，行、列的编号都是 \(0\) 到 \(N\)。

• 若有变量 \(\color{blue} p_{i,j}\) 则 \(\color{blue} S_{i,j} = p_{i,j}\)。
• 若无变量 \(\color{blue} p_{i,j}\) 则 \(\color{blue} S_{i,j} = 0\)。

用矩阵 \(\color{blue} S\)，我们可以构造出一个 \(N\) 行 \(N\) 列的矩阵 \(\color{blue} A\)，行、列的编号都是 \(1\) 到 \(N\)。

\[\color{blue} A_{i,j} = S_{i,j} + S_{i - 1, j} + S_{i, j - 1} + S_{i-1, j-1}\]

矩阵 \(\color{blue} A\) 满足：

• 对所有 \(1 \le r_1 \le r_2 \le N\)、\(1 \le c_1 \le c_2 \le N\) 都有：子矩阵 \(\color{blue} A_{r_1.. r_2, c_1 .. c_2}\) 里的元素之和等于 \(\color{blue} S_{r_2, c_2} + S_{r_2, c_1 - 1} + S_{r_1 - 1, c_2} + S_{r_1 - 1, c_1 - 1}\)。

于是，矩阵 \(\color{blue} A\) 满足：

• 每个 \(1\) 型区域里的元素之和都是 \(\color{blue} 0\)。
• 每个 \(2\) 型区域里的元素之和都是 \(\color{blue} 1\)。

这正是我们想要的，这样就足够了。

有了矩阵 \(\color{blue} A\)，我们就可以构造所求的矩阵 \(X\)：

• 若 \(X_{i,j}\) 未被 \(1\) 型条件或 \(2\) 型条件覆盖，则 \(X_{i,j} = 0\)。
• 否则若 \(\color{blue} A_{i,j} = 0\)，则 \(X_{i,j} = 1\)，若 \(\color{blue} A_{i,j} = 1\)，则 \(X_{i,j} = 2\)。

核

这道题的“核”是这样一个事实：考虑一个交换群 \(G\)。对于每个矩阵 \(A\)，存在唯一的矩阵 \(B\) 满足：\(B\) 的二维前缀和矩阵等于 \(A\)。这里，\(A\)、\(B\) 的元素都来自 \(G\) 且所谓“前缀和”的加法就是 \(G\) 的运算。