← 返回题目列表

Codeforces · 2043/E

E. 矩阵变换

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

给定两个矩阵 $$$A$$$ 和 $$$B$$$,大小为 $$$n \times m$$$,填充 $$$0$$$ 和 $$$10^9$$$ 之间的整数。您可以按任意顺序和任意次数对矩阵 $$$A$$$ 执行以下操作:

- &=:选择两个整数 $$$i$$$ 和 $$$x$$$ ($$$1 \le i \le n$$$, $$$x \ge 0$$$) 并将 $$$i$$$ 行中的每个元素替换为 $$$x$$$ 与该元素之间按位 AND 运算的结果。形式上,对于 [1, m]$$$ 中的每个 $$$j \in,元素 $$$A_{i,j}$$$ 被替换为 $$$A_{i,j} \text{ & } x$$$;
- |=:选择两个整数 $$$j$$$ 和 $$$x$$$ ($$$1 \le j \le m$$$, $$$x \ge 0$$$) 并将 $$$j$$$ 列中的每个元素替换为 $$$x$$$ 与该元素之间按位 OR 运算的结果。形式上,对于 [1, n]$$$ 中的每个 $$$i \in,元素 $$$A_{i,j}$$$ 被替换为 $$$A_{i,j} \text{ | } x$$$。

对于不同的操作,$$$x$$$ 的值可以选择不同的值。

确定是否可以使用给定操作任意次数(包括零次)将矩阵 $$$A$$$ 转换为矩阵 $$$B$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。然后,$$$t$$$ 测试用例如下。

每个测试用例给出如下:

- 第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 10^3$$$; $$$n \cdot m \le 10^3$$$) - 矩阵 $$$A$$$ 和 $$$B$$$ 的维度;
- 以下 $$$n$$$ 行描述矩阵 $$$A$$$,其中第 $$$i$$$ 行包含整数 $$$A_{i,1}, A_{i,2}, \dots, A_{i,m}$$$ ($$$0 \le A_{i,j} \le 10^9$$$);
- 以下 $$$n$$$ 行描述矩阵 $$$B$$$,其中第 $$$i$$$ 行包含整数 $$$B_{i,1}、B_{i,2}、\dots、B_{i,m}$$$ ($$$0 \le B_{i,j} \le 10^9$$$)。

输出

对于每个测试用例,如果可以将矩阵 $$$A$$$ 转换为矩阵 $$$B$$$,则输出 Yes;每个字母可以任意大小写输出,无论大写还是小写。

示例

输入 #1

4
1 1
12
13
2 2
10 10
42 42
21 21
21 21
2 2
74 10
42 106
21 85
85 21
2 4
1 2 3 4
5 6 7 8
3 2 3 4
1 0 1 0

输出 #1

Yes
Yes
No
Yes

注意

让我们考虑第二组输入数据并显示将矩阵 $$$A$$$ 转换为矩阵 $$$B$$$ 的操作序列:

最初,矩阵如下所示:

$$$\begin{bmatrix} 10&10\\ 42&42\\ \end{bmatrix}$$$

使用参数 $$$i = 1$$$ 和 $$$x = 0$$$ 应用第一种类型的操作。结果,我们得到矩阵:

$$$\begin{bmatrix} 0&0\\ 42&42\\ \end{bmatrix}$$$

使用参数 $$$i = 2$$$ 和 $$$x = 0$$$ 应用第一种类型的操作。结果,我们得到矩阵:

$$$\begin{bmatrix} 0&0\\ 0&0\\ \end{bmatrix}$$$

使用参数 $$$j = 1$$$ 和 $$$x = 21$$$ 应用第二种类型的操作。结果,我们得到矩阵:

$$$\begin{bmatrix} 21&0\\ 21&0\\ \end{bmatrix}$$$

使用参数 $$$j = 2$$$ 和 $$$x = 21$$$ 应用第二种类型的操作。结果,我们得到矩阵:

$$$\begin{bmatrix} 21&21\\ 21&21\\ \end{bmatrix}$$$

因此,我们将矩阵 $$$A$$$ 转换为矩阵 $$$B$$$。