P10102 [GDKOI2023 Senior] Matrix

You are given three $n \times n$ matrices $A$, $B$, and $C$ multiple times. You need to determine whether $A \times B$ is equal to $C$ modulo $998244353$. Here, $\times$ denotes matrix multiplication, and $C_{i,j} = \sum_{k=1}^{n} A_{i,k} B_{k,j}$. The input size of this problem is large, so fast input reading is recommended.

The first line contains a positive integer $T$, the number of test cases. Then there are $T$ test cases. In each test case, the first line contains a positive integer $n$, the matrix size. The next $n$ lines each contain $n$ integers, describing matrix $A$. The next $n$ lines each contain $n$ integers, describing matrix $B$. The next $n$ lines each contain $n$ integers, describing matrix $C$.

Output $T$ lines, each being `Yes` or `No`, indicating whether $A \times B$ is equal to $C$ modulo $998244353$.

For $20\%$ of the testdata, $\sum n \le 300$. For another $20\%$ of the testdata, the number of positions where $A_{i,j} \ne 0$ does not exceed $n$. For $100\%$ of the testdata, $1 \le T, n \le 3000$, $\sum n \le 3000$, and $0 \le A_{i,j}, B_{i,j}, C_{i,j} < 998244353$. Translated by ChatGPT 5