自动搬运

查看原文

来自洛谷，原作者为

	蒟蒻君HJT I am one with the Force; The Force is with me.

搬运于2025-08-24 22:54:41，当前版本为作者最后更新于2024-01-23 16:47:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

套路题，随机一个 $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}$，是可以接受的。