#P5808. [GDKOI2023 提高组] 矩阵

[GDKOI2023 提高组] 矩阵

题目描述

对于每组数据,给定三个 n×nn\times n 的矩阵 A,B,CA,B,C。判断对每个 i,ji,j 是否都有

$$\sum_{k=1}^{n} A_{i,k} B_{k,j} \equiv C_{i,j}\pmod{998244353}.$$

本题读入量较大,建议使用快速读入。

输入格式

从标准输入读入数据。第一行输入一个正整数 TT,表示数据组数。

接下来包含 TT 组数据,每组数据第一行为一个正整数 nn,表示矩阵大小。

接下来 nn 行,每行 nn 个整数,表示矩阵 AA。

接下来 nn 行,每行 nn 个整数,表示矩阵 BB。

接下来 nn 行,每行 nn 个整数,表示矩阵 CC。

输出格式

向标准输出写 TT 行。对于每组数据,等式成立时输出 Yes,否则输出 No。

样例 #1

样例输入 #1

3
1
2
3
6
2
1 2
3 4
5 6
7 8
19 22
43 51
2
1111111 2222222
3333333 4444444
5555555 6666666
7777777 8888888
39625305 256038638
772687616 944903942

样例输出 #1

Yes
No
Yes

提示

对于 20% 的数据,满足 ∑n≤300\sum n \le 300。

对于另外 20% 的数据,满足 Ai,j≠0A_{i,j} \ne 0 的位置不超过 nn 个。

对于 100% 的数据,满足 $1 \le T, n \le 3000,\sum n \le 3000, 0 \le A_{i,j} , B_{i,j} , C_{i,j} < 998244353$。

本题判断的是模 998244353998244353 的矩阵等式,而不是普通整数乘积相等。