题目分析

本题是一个矩阵乘法验证问题：给定三个 $n \times n$ 矩阵 $A,B,C$，需要判断在模 $998244353$ 意义下是否满足 $A \times B = C$。

---

直接方法的不可行性

最直接的想法是计算 $D = A \times B$，然后逐元素比较 $D$ 和 $C$。矩阵乘法的标准算法时间复杂度为 $O(n^3)$。

计算复杂度分析：

• 单组数据：$O(n^3)$
• 多组数据：$\sum n \le 3000$，但 $n$ 最大可达 $3000$
• 最坏情况：$n=3000$，$n^3 = 27 \times 10^9$ 次运算，显然不可行

即使使用 Strassen 算法（$O(n^{2.81})$）或其他快速矩阵乘法，对于 $n=3000$ 仍然太慢。

---

随机化算法的引入

Freivalds 算法（1979）

Freivalds 提出了一种概率算法来验证矩阵乘积，核心思想是：

引理：如果 $A \times B \neq C$，那么对于随机向量 $r$（分量在 $\{0,1\}$ 中均匀选取），有 $ \Pr[(A \times B - C) \times r = 0] \le \frac{1}{2} $

算法步骤

1. 随机生成 $n$ 维列向量 $r$，每个分量独立随机取 $0$ 或 $1$
2. 计算 $P = A \times (B \times r) - C \times r$
3. 如果 $P$ 是全零向量，则可能 $A \times B = C$
4. 如果 $P$ 不是全零向量，则一定 $A \times B \neq C$
5. 重复 $k$ 次以上过程，如果所有 $k$ 次 $P$ 都是全零向量，则判断 $A \times B = C$

错误概率分析

• 如果 $A \times B = C$，算法总是输出正确（全零向量）
• 如果 $A \times B \neq C$，设 $D = A \times B - C \neq 0$
  • $D$ 至少有一行非零，设为第 $i$ 行
  • 考虑 $D \times r$ 的第 $i$ 个分量：$(Dr)_i = \sum_{j=1}^n D_{i,j} r_j$
  • 这是一个关于 $r_j$ 的线性函数
  • 根据 Schwartz-Zippel 引理（有限域版本），当 $r$ 随机时，这个和为 $0$ 的概率不超过 $1/2$
• 重复 $k$ 次，错误概率 $\le (1/2)^k$

时间复杂度

• 计算 $B \times r$：$O(n^2)$
• 计算 $A \times (Br)$：$O(n^2)$
• 计算 $C \times r$：$O(n^2)$
• 每次验证：$O(n^2)$
• 重复 $k$ 次：$O(kn^2)$

对于 $n=3000$，$k=30$，大约 $30 \times 9 \times 10^6 = 2.7 \times 10^8$ 次运算，可以接受。

---

算法优化与实现细节

1. 随机数生成

• 使用 rand() 或更高质量的随机数生成器
• 每个分量取 $0$ 或 $1$ 即可，也可以取更大的范围（如 $0$ 到 $998244352$），但 $\{0,1\}$ 最简单
• 使用 $\{0,1\}$ 时，错误概率上界为 $1/2$

2. 模运算优化

模 $998244353$ 的运算：

• 这是一个质数，有利于模运算
• 可以使用 unsigned long long 避免中间结果溢出
• 乘法后立即取模

3. 计算顺序优化

为了减少常数因子：

• 先计算 $v = B \times r$
• 再计算 $u = A \times v$
• 最后计算 $w = C \times r$
• 比较 $u$ 和 $w$

4. 重复次数选择

• 理论保证：$k=30$ 时错误概率 $\le (1/2)^{30} \approx 9.3 \times 10^{-10}$
• 实际中 $k=10$ 或 $20$ 通常足够
• 竞赛中常取 $k=3$ 到 $5$（在时限和正确率间权衡）

---

正确性证明的数学细节

引理形式化

设 $D = A \times B - C \neq 0$，则存在 $i,j$ 使得 $D_{i,j} \neq 0$。

考虑 $D \times r$ 的第 $i$ 个分量： $(D r)_i = \sum_{j=1}^n D_{i,j} r_j$ 这是一个非零线性函数（因为 $D_{i,j}$ 不全为零）。

有限域上的 Schwartz-Zippel 引理

对于有限域 $\mathbb{F}_p$ 上的非零 $n$ 元线性函数 $f(r_1,\dots,r_n)$，如果每个 $r_i$ 独立均匀随机选取，则 $\Pr[f(r_1,\dots,r_n) = 0] \le \frac{1}{p}$ 在我们的情况中，如果 $r_i \in \{0,1\}$，这实际上是 $\mathbb{F}_2$ 上的函数，但模 $998244353$ 是模运算。更准确地说：

如果 $r_i$ 取 $\{0,1\}$，那么 $(Dr)_i = 0$ 的概率：

• 设 $S = \{j \mid D_{i,j} \neq 0\}$
• $(Dr)_i = \sum_{j \in S} D_{i,j} r_j$
• 固定其他 $r_j$，最后一个 $r_k$（$k \in S$）使总和为 $0$ 的概率 $\le 1/2$

因此总体概率 $\le 1/2$。

---

扩展与变体

1. 使用更大的随机域

如果让 $r_i$ 在 $\{0,1,\dots,p-1\}$ 中均匀随机选取（$p=998244353$），则错误概率 $\le 1/p$，一次测试就足够。但这样需要大整数运算，可能更慢。

2. 确定化算法

是否存在 $O(n^2)$ 的确定算法？这是一个开放问题。已知：

• 如果使用代数复杂度理论，矩阵乘法验证与矩阵乘法本身复杂度相当
• 但在实践中，随机化算法是唯一可行的方法

3. 稀疏矩阵优化

对于题目中“$A_{i,j} \ne 0$ 的位置不超过 $n$ 个”的子任务：

• 可以特殊处理，复杂度可能低于 $O(n^2)$
• 但 Freivalds 算法仍适用且简单

---

实际竞赛中的应用

1. 本题的特殊性

• $\sum n \le 3000$ 是关键：虽然单组 $n$ 可达 $3000$，但总规模有限
• 这意味着 $O(n^2)$ 算法总复杂度为 $O((\sum n) \times n_{\max}) \approx 3000 \times 3000 = 9 \times 10^6$ 量级
• 加上 $k=30$ 的常数，大约 $2.7 \times 10^8$ 次运算

2. 实现注意事项

• 必须使用快速 I/O（题目提示）
• 注意模运算的常数优化
• 向量乘法可以使用循环展开
• 随机数质量：使用 mt19937 更好

3. 样例分析

以样例第二组为例：

A = [1 2; 3 4], B = [5 6; 7 8]
A×B = [19 22; 43 50]  # 注意：50 而不是 51
给定的 C = [19 22; 43 51]
所以不相等，算法应能检测到

---

算法总结

Freivalds 算法的核心优势：

1. 理论保证：错误概率可控制，可以通过重复任意降低
2. 时间复杂度：$O(n^2)$ 而非 $O(n^3)$
3. 实现简单：只需实现矩阵乘向量
4. 空间友好：只需 $O(n)$ 额外空间

算法步骤：

对于每组数据：
  读入 n, A, B, C
  对于 t = 1 到 K（如 K=30）：
    生成随机向量 r[1..n] ∈ {0,1}
    计算 v = B × r
    计算 u = A × v
    计算 w = C × r
    如果 u ≠ w：
      输出 "No" 并跳到下一组
  如果所有测试都通过：
    输出 "Yes"

复杂度：$O(K \cdot n^2)$，对于本题数据范围完全可行。

---

结论

本题展示了随机化算法在解决大规模计算问题中的强大威力。通过巧妙的概率设计，我们将一个 $O(n^3)$ 的问题转化为 $O(n^2)$ 的可解问题，这是理论计算机科学与算法竞赛结合的典范。

Freivalds 算法不仅是矩阵验证的有效工具，其思想——用随机向量“探测”矩阵性质——也在其他领域有广泛应用，如流算法、属性测试等。这道题很好地体现了“有时验证比计算更容易”的计算思维。