#SYUCT13H. 矩阵化装
矩阵化装
题目描述
塔卫二的前线建设依赖终末地工业的集成工业系统。位于人工静止轨道上的帝江号负责管理协议源石,并向地面设施同步生产协议。
不同设施的接口排列方式并不相同。为了让同一份协议适配不同接口,帝江号允许对协议矩阵进行若干次“接口变换”。
一份协议用一个 的矩阵表示。你可以把它看成一张有 行、 列的数字表:行表示发送通道,列表示接收通道,行和列均从 开始编号。
令
矩阵中的所有元素都属于 ,每次加法和乘法都对 取模。
下面用 表示正在变换的矩阵。一次接口变换只能执行以下六类操作之一:
-
选择 ,交换第 行与第 行;
-
选择第 行和一个整数 (),执行
$$M_{i,k}\leftarrow cM_{i,k}\pmod P \qquad(1\le k\le n);$$ -
选择 和一个整数 (),执行
$$M_{i,k}\leftarrow M_{i,k}+cM_{j,k}\pmod P \qquad(1\le k\le n);$$ -
选择 ,交换第 列与第 列;
-
选择第 列和一个整数 (),执行
$$M_{k,i}\leftarrow cM_{k,i}\pmod P \qquad(1\le k\le n);$$ -
选择 和一个整数 (),执行
$$M_{k,i}\leftarrow M_{k,i}+cM_{k,j}\pmod P \qquad(1\le k\le n).$$
以上操作可以进行任意多次,也可以一次都不进行。
例如,若当前矩阵为
把第 行的 倍加到第 行后,矩阵变为
现在给定两个协议矩阵 和 。请判断:从 出发,是否可以通过上述接口变换得到 。你只需要回答能否做到,不需要输出具体的操作过程。
你不需要了解“可逆矩阵”或矩阵乘法;只需按照题面给出的六类操作判断即可。
输入格式
第一行输入一个整数 (),表示测试数据组数。
对于每组测试数据:
- 第一行输入一个整数 ();
- 接下来 行,每行输入 个整数,描述协议矩阵 ;
- 再接下来 行,每行输入 个整数,描述协议矩阵 。
矩阵中的每个元素 均满足 。
保证所有测试数据中的 之和不超过 。
输出格式
对于每组测试数据输出一行:
- 如果可以从 通过上述操作得到 ,输出
YES; - 否则输出
NO。
输出字母大小写不敏感。
样例
4
2
1 0
0 0
0 1
0 0
2
1 0
0 1
1 0
0 0
3
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
2
1 2
2 4
1 1
1 1
YES
NO
YES
YES
提示
第一组数据只需交换矩阵 的两列,就可以得到矩阵 。
第三组数据中的两个矩阵都是全零矩阵,因此不进行任何操作即可得到目标矩阵。
- 本题中的加法和乘法都对 取模。例如,。
- 是质数,因此模 意义下的每个非零元素都有乘法逆元。
- 以上六类操作都不会永久丢失原矩阵中的信息;每次操作都存在一种允许的操作可以将它撤销。