P10102 [GDKOI2023 提高组] 矩阵 题解

· · 题解

套路题，随机一个 n\times 1 的向量 x，检验 A\times B\times x 和 C\times x 是否相等即可。

为什么这样做是对的？设 M=998244353，每维取值为 [0,M-1] 中整数的向量构成的空间为 \mathbb{Z}^n，加法和数乘定义为模 M 意义下的运算。

上述做法等价于检验 (A\times B-C)x 是否等于 0，即 x 是否在 A\times B-C 的零空间 N(A\times B - C) 中。如果 A\times B-C\neq 0，则这个矩阵的秩至少为 1，由 rank-nullity 定理得 \operatorname{dim}(N(A\times B - C))\leq n-1，\mathbb{Z}^n 中的向量个数为 M^{n}，而其维数为 d 的子空间中的向量个数为 M^d，所以此时选到令 (A\times B-C)x=0 的 x 的概率不超过 M^{d-n}\leq M^{-1}，是可以接受的。