【2017 X Samara Regional Intercollegiate Programming Contest I】Matrix God 题解

题目大意

  有三个 $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$得：

$$(AB-C)\vec v=0$$

  这表示 $\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$，则可以随机少一些。