BZOJ 2396 神奇的矩阵


题目链接: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 中元素我们随机获得,然后判定是否相等... 为了避免错误,可以进行多次判定,实际上,只判定一次也能过掉这道题...

代码如下:

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 2396 神奇的矩阵


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: ,