AT_abc276_h [ABC276Ex] Construct a Matrix

题目描述

判断是否存在一个满足以下条件的 $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$。

输入格式

输入以如下格式从标准输入给出。

$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，接下来的 $N$ 行输出 $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}$

如果存在多个满足条件的 $X$，输出任意一个即可。

输入输出样例 #1

输入 #1

2 3
1 1 1 2 0
1 2 2 2 1
2 2 1 2 2

输出 #1

Yes
0 2
1 2

输入输出样例 #2

输入 #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

说明/提示

限制条件

• $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\}$
• 输入均为整数

样例解释 1

例如对于 $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,3$ 也可以验证满足条件。

由 ChatGPT 4.1 翻译