BZOJ 2396 神奇的矩阵

发布于 2017-04-20  241 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2396

题意:给出若干组数据,对于每组数据,有 A,B,C 三个矩阵,问 A*B 是否等于 C...


暴力的做法是 n3 的... 所以考虑一些神奇的东西

我们知道矩阵乘法是不满足消去律的... 所以 A*B*R=C*R 不能推导出 A*B=C 但是实际上,若前式成立,对于随机数据,后式是有很大概率成立的.

所以我们将等式两边同乘一个 1*n 的矩阵 R,R 中元素我们随机获得,然后判定是否相等... 为了避免错误,可以进行多次判定,实际上,只判定一次也能过掉这道题...

代码如下:

 


一个非常弱的准退役OIER