← 返回题目列表

AtCoder · past202306_l

L. 位矩阵

中文机器翻译题面 查看原题

问题陈述

您将获得 H-by-W 矩阵 A 由非负整数组成。

您可以执行以下操作任意次数(可能为零):

  • 选择一个整数 i 满意 1 \le i \le H 和一个非负整数 X,并替换每个元素 A_{i,j} 在 i矩阵的第行 A 与 A_{i,j}\ \mathrm{XOR}\ X.
  • 选择一个整数 j 满意 1 \le j \le W 和一个非负整数 X,并替换每个元素 A_{i,j} 在 j矩阵的第列 A 与 A_{i,j}\ \mathrm{XOR}\ X.

您还获得了 H-by-W 矩阵 B 由非负整数和 -1.

确定是否可以使 A_{i,j}=B_{i,j} 对于所有整数对 (i,j) 这样 B_{i,j} \neq -1 通过执行操作。

什么是 \mathrm{XOR}?

按位 \mathrm{XOR} 非负整数 A, B,表示为 A \oplus B,定义如下:

  • 的 树的 2^k (k \geq 0) 地点 A \oplus B 的二进制表示法是 1 如果恰好是其中之一 2^k 的地方 A 和 B 的二进制表示法是 1,和 0 否则。
例如, 3 \oplus 5 = 6 (二进制表示法: 011 \oplus 101 = 110).
一般来说,按位 \mathrm{XOR} of k 整数 p_1, p_2, p_3, \dots, p_k 定义为 (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k),并且可以证明这不取决于顺序 p_1, p_2, p_3, \dots p_k.

约束

  • 1 \le H,W \le 500
  • 0 \le A_{i,j} < 2^{30}
  • -1 \le B_{i,j} < 2^{30}
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

H W
A_{1,1} A_{1,2} \dots A_{1,W}
A_{2,1} A_{2,2} \dots A_{2,W}
\vdots
A_{H,1} A_{H,2} \dots A_{H,W}
B_{1,1} B_{1,2} \dots B_{1,W}
B_{2,1} B_{2,2} \dots B_{2,W}
\vdots
B_{H,1} B_{H,2} \dots B_{H,W}

输出

如果可以满足条件,则打印 Yes;否则,打印 No.


示例输入 1

2 2
1 2
3 4
-1 3
1 7

示例输出 1

Yes

最初, A 如下:

1 2
3 4

执行操作 X=1 在第二列中,我们得到:

1 3
3 5

执行操作 X=2 在第二行,我们得到:

1 3
1 7

因此,可以满足条件,所以打印 Yes.


示例输入 2

2 2
1 2
3 4
5 3
1 7

示例输出 2

No

这种情况无论如何都不可能满足条件,所以打印 No.