[GDKOI2023 提高组] 矩阵

Luogu

IDLGP10102

Time2000ms

Memory1024MB

DifficultyP5

2023广东随机化

多次给定三个 $n \times n$ 的矩阵 $A, B, C$，你需要判断 $A \times B$ 在模 $998244353$ 意义下是否等于 $C$。其中 $×$ 为矩阵乘法，$C_{i,j} = \sum_{k=1}^{n}A_{i,k}B_{k,j}$。本题读入量较大，建议使用快速读入。 ## Input 第 $1$ 行输入一个正整数 $T$，表示数据组数。接下来包含 $T$ 组数据，每组数据第一行为一个正整数 $n$，表示矩阵大小。接下来 $n$ 行，每行 $n$ 个整数，表示矩阵 $A$。接下来 $n$ 行，每行 $n$ 个整数，表示矩阵 $B$。接下来 $n$ 行，每行 $n$ 个整数，表示矩阵 $C$。 ## Output 输出 $T$ 行 Yes 或 No，表示 $A \times B$ 在模 $998244353$ 意义下是否等于 $C$。 [samples] ## Note 对于 20% 的数据，满足 $\sum n ≤ 300$。对于另外 20% 的数据，满足 $A_{i,j} \ne 0$ 的位置不超过 $n$ 个。对于 100% 的数据，满足 $1 ≤ T, n ≤ 3000,\sum n ≤ 3000, 0 ≤ A_{i,j} , B_{i,j} , C_{i,j} < 998244353$。

Samples

Input #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

Output #1

Yes
No
Yes

API Response (JSON)

{
  "problem": {
    "name": "[GDKOI2023 提高组] 矩阵",
    "description": {
      "content": "多次给定三个 $n \\times n$ 的矩阵 $A, B, C$，你需要判断 $A \\times  B$ 在模 $998244353$ 意义下是否等于 $C$。 其中 $×$ 为矩阵乘法，$C_{i,j} = \\sum_{k=1}^{n}A_{i,k}B_{k,j}$。 本题读入量较大，建议使用快速读入。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10102"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "多次给定三个 $n \\times n$ 的矩阵 $A, B, C$，你需要判断 $A \\times  B$ 在模 $998244353$ 意义下是否等于 $C$。\n其中 $×$ 为矩阵乘法，$C_{i,j} = \\sum_{k=1}^{n}A_{i,k}B_{k,j}$。\n\n本题读入量较大，建议使用快速读入。\n\n## Input\n\n第 $1$ 行输入一个正整数 $T$，表示数据组数。\n\n接下来包含...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments