102767: [AtCoder]ABC276 Ex - Construct a Matrix
Description
Score : $600$ points
Problem Statement
Determine whether there is an $N$-by-$N$ matrix $X$ that satisfies the following conditions, and present one such matrix if it exists. (Let $x_{i,j}$ denote the element of $X$ at the $i$-th row from the top and $j$-th column from the left.)
- $x_{i,j} \in \{ 0,1,2 \}$ for every $i$ and $j$ $(1 \leq i,j \leq N)$.
- The following holds for each $i=1,2,\ldots,Q$.
- Let $P = \prod_{a_i \leq j \leq b_i} \prod_{c_i \leq k \leq d_i} x_{j,k}$. Then, $P$ is congruent to $e_i$ modulo $3$.
Constraints
- $1 \leq N,Q \leq 2000$
- $1 \leq a_i \leq b_i \leq N$
- $1 \leq c_i \leq d_i \leq N$
- $e_i \in \{0,1,2 \}$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $Q$ $a_1$ $b_1$ $c_1$ $d_1$ $e_1$ $\vdots$ $a_Q$ $b_Q$ $c_Q$ $d_Q$ $e_Q$
Output
If no matrix $X$ satisfies the conditions, print No.
If there is a matrix $X$ that satisfies them, print Yes in the first line and one such instance of $X$ in the following format in the second and subsequent lines.
$x_{1,1}$ $x_{1,2}$ $\ldots$ $x_{1,N}$
$x_{2,1}$ $x_{2,2}$ $\ldots$ $x_{2,N}$
$\vdots$
$x_{N,1}$ $x_{N,2}$ $\ldots$ $x_{N,N}$
If multiple matrices satisfy the conditions, any of them will be accepted.
Sample Input 1
2 3 1 1 1 2 0 1 2 2 2 1 2 2 1 2 2
Sample Output 1
Yes 0 2 1 2
For example, for $i=2$, we have $P = \prod_{a_2 \leq j \leq b_2} \prod_{c_2 \leq k \leq d_2} x_{j,k}= \prod_{1 \leq j \leq 2} \prod_{2 \leq k \leq 2} x_{j,k}=x_{1,2} \times x_{2,2}$.
In this sample output, we have $x_{1,2}=2$ and $x_{2,2}=2$, so $P=2 \times 2 = 4$, which is congruent to $e_2=1$ modulo $3$.
It can be similarly verified that the condition is also satisfied for $i=1$ and $i=3$.
Sample Input 2
4 4 1 4 1 4 0 1 4 1 4 1 1 4 1 4 2 1 4 1 4 0
Sample Output 2
No
Input
题意翻译
给定 $ N, Q $ 以及 $ Q $ 条限制，存在 $ N \times N $ 的 $ 0, 1, 2 $ 矩阵（即矩阵中只能有 $ 0, 1, 2 $），每条限制包含 $ a, b, c, d, e $，表示 $ [a, b] $ 行 $ [c, d] $ 列的子矩阵（或者说左上角为 $ (a, c) $ 右下角为 $ b, d $ 的子矩阵）所有元素之积模 $ 3 $ 后等于 $ e $，你需要构造一个满足这 $ Q $ 条限制的 $ N \times N $ 矩阵。无解输出 `No`，反之输出 `Yes` 并输出矩阵。存在 SPJ。Output
问题描述
判断是否存在一个满足以下条件的$N$乘$N$矩阵$X$，如果存在则给出其中一个矩阵。（设$x_{i,j}$为$X$中从上数第$i$行、从左数第$j$列的元素。）
- 对于所有的$i$和$j$ $(1 \leq i,j \leq N)$，有$x_{i,j} \in \{ 0,1,2 \}$。
- 对于每一个$i=1,2,\ldots,Q$，有以下结论成立：
- 设$P = \prod_{a_i \leq j \leq b_i} \prod_{c_i \leq k \leq d_i} x_{j,k}$。则$P$除以$3$的余数等于$e_i$。
限制条件
- $1 \leq N,Q \leq 2000$
- $1 \leq a_i \leq b_i \leq N$
- $1 \leq c_i \leq d_i \leq N$
- $e_i \in \{0,1,2 \}$
- 输入中的所有值都是整数。
输入
输入通过标准输入给出，格式如下：
$N$ $Q$ $a_1$ $b_1$ $c_1$ $d_1$ $e_1$ $\vdots$ $a_Q$ $b_Q$ $c_Q$ $d_Q$ $e_Q$
输出
如果没有矩阵$X$满足条件，则打印No。
如果存在一个满足条件的矩阵$X$，则在第一行打印Yes，然后在接下来的第二行和后续行中以以下格式打印一个$X$的实例：
$x_{1,1}$ $x_{1,2}$ $\ldots$ $x_{1,N}$
$x_{2,1}$ $x_{2,2}$ $\ldots$ $x_{2,N}$
$\vdots$
$x_{N,1}$ $x_{N,2}$ $\ldots$ $x_{N,N}$
如果有多个矩阵满足条件，接受其中任意一个。
样例输入1
2 3 1 1 1 2 0 1 2 2 2 1 2 2 1 2 2
样例输出1
Yes 0 2 1 2
例如，对于$i=2$，我们有$P = \prod_{a_2 \leq j \leq b_2} \prod_{c_2 \leq k \leq d_2} x_{j,k}= \prod_{1 \leq j \leq 2} \prod_{2 \leq k \leq 2} x_{j,k}=x_{1,2} \times x_{2,2}$。
在这个样例输出中，我们有$x_{1,2}=2$和$x_{2,2}=2$，所以$P=2 \times 2 = 4$，它除以$3$的余数等于$e_2=1$。
可以类似地验证条件对于$i=1$和$i=3$也成立。
样例输入2
4 4 1 4 1 4 0 1 4 1 4 1 1 4 1 4 2 1 4 1 4 0
样例输出2
No