题目大意
有三个 $n\times n$ 的矩阵 $A$、$B$、$C$，问 $A\times B$ 是否等于 $C$。
元素在模 $10^9+7$ 意义下。
$n \leq 1000$
题解
新套路 get。
直接矩阵乘法 $O(n^3)$ 很大，考虑把这个降下来。
随机几个 $n\times 1$ 的向量，比如是 $\vec v$，那么就是判断 $AB\vec v$ 是否等于 $C \vec v$。
这样矩阵乘法就是 $O(n^2)$ 的了！！！
证明
UPD：终于在多年以后的毛营学到了证明 qaq
如何分析这个算法的正确率呢？
如果 $\exists \vec v \not= 0$，使得 $AB \vec v \not= C \vec v$，那么 $AB$ 一定不等于 $C$。
也就是说，我们的算法错误意味着 $\exists \vec v\not= 0$，$AB \vec v=C \vec v$ 但 $AB\not= C$。由 $AB \vec v=C \vec v$ 得：
这表示 $\vec v∈Nul(AB-C)$。但由于 $AB-C\not=0$，所以 $Rank(AB-C)>0$，$\dim Nul(AB-C)<n$。因此，随机到一个这样一个向量 $\vec v$ 的概率是 $\frac{小于n维的空间}{n维空间}$，也就是 $0$。
也就是说，理论上，当矩阵内的数的取值是任意实数的话，只用随机一次就够了。
但很多时候矩阵内的数的取值是有限制的。例如，规定三个矩阵都是 01 矩阵，运算在 $\bmod 2$ 意义下，那么 $\frac{小于n维的空间}{n维空间}$ 就不能说等于 $0$ 了，而只能说是小于 $\frac{1}{2}$。因此，要随机多几次，比如 10 次，使得错误概率 $P_{wrong}<(\frac{1}{2})^{10}=\frac{1}{1024}$。
当矩阵内的数的取值范围逐渐增大时，$\frac{小于n维的空间}{n维空间}$ 越来越接近于 $0$，则可以随机少一些。