#SYUCT13H. 矩阵化装

矩阵化装

题目描述

塔卫二的前线建设依赖终末地工业的集成工业系统。位于人工静止轨道上的帝江号负责管理协议源石,并向地面设施同步生产协议。

不同设施的接口排列方式并不相同。为了让同一份协议适配不同接口,帝江号允许对协议矩阵进行若干次“接口变换”。

一份协议用一个 n×nn\times n 的矩阵表示。你可以把它看成一张有 nn 行、nn 列的数字表:行表示发送通道,列表示接收通道,行和列均从 11 开始编号。

令

P=998244353.P=998244353.

矩阵中的所有元素都属于 {0,1,…,P−1}\{0,1,\ldots,P-1\},每次加法和乘法都对 PP 取模。

下面用 MM 表示正在变换的矩阵。一次接口变换只能执行以下六类操作之一:

  1. 选择 i≠ji\ne j,交换第 ii 行与第 jj 行;

  2. 选择第 ii 行和一个整数 cc(1≤c<P1\le c<P),执行

    $$M_{i,k}\leftarrow cM_{i,k}\pmod P \qquad(1\le k\le n);$$
  3. 选择 i≠ji\ne j 和一个整数 cc(0≤c<P0\le c<P),执行

    $$M_{i,k}\leftarrow M_{i,k}+cM_{j,k}\pmod P \qquad(1\le k\le n);$$
  4. 选择 i≠ji\ne j,交换第 ii 列与第 jj 列;

  5. 选择第 ii 列和一个整数 cc(1≤c<P1\le c<P),执行

    $$M_{k,i}\leftarrow cM_{k,i}\pmod P \qquad(1\le k\le n);$$
  6. 选择 i≠ji\ne j 和一个整数 cc(0≤c<P0\le c<P),执行

    $$M_{k,i}\leftarrow M_{k,i}+cM_{k,j}\pmod P \qquad(1\le k\le n).$$

以上操作可以进行任意多次,也可以一次都不进行。

例如,若当前矩阵为

M=(1234),M= \begin{pmatrix} 1&2\\ 3&4 \end{pmatrix},

把第 11 行的 22 倍加到第 22 行后,矩阵变为

M=(1258).M= \begin{pmatrix} 1&2\\ 5&8 \end{pmatrix}.

现在给定两个协议矩阵 AA 和 BB。请判断:从 AA 出发,是否可以通过上述接口变换得到 BB。你只需要回答能否做到,不需要输出具体的操作过程。

你不需要了解“可逆矩阵”或矩阵乘法;只需按照题面给出的六类操作判断即可。

输入格式

第一行输入一个整数 TT(1≤T≤1001\le T\le 100),表示测试数据组数。

对于每组测试数据:

  • 第一行输入一个整数 nn(1≤n≤31\le n\le 3);
  • 接下来 nn 行,每行输入 nn 个整数,描述协议矩阵 AA;
  • 再接下来 nn 行,每行输入 nn 个整数,描述协议矩阵 BB。

矩阵中的每个元素 xx 均满足 0≤x<P0\le x<P。

保证所有测试数据中的 nn 之和不超过 300300。

输出格式

对于每组测试数据输出一行:

  • 如果可以从 AA 通过上述操作得到 BB,输出 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

提示

第一组数据只需交换矩阵 AA 的两列,就可以得到矩阵 BB。

第三组数据中的两个矩阵都是全零矩阵,因此不进行任何操作即可得到目标矩阵。

  • 本题中的加法和乘法都对 PP 取模。例如,(998244352+2) mod P=1(998244352+2)\bmod P=1。
  • P=998244353P=998244353 是质数,因此模 PP 意义下的每个非零元素都有乘法逆元。
  • 以上六类操作都不会永久丢失原矩阵中的信息;每次操作都存在一种允许的操作可以将它撤销。

下载正式赛最终版 PDF 题面