首页 > 其他 > 详细

bzoj1040 矩阵相乘结果的判断

时间:2017-12-24 19:56:41      阅读:254      评论:0      收藏:0      [点我收藏+]

给出三个N*N的矩阵A, B, C,问A * B是否等于C?
Input
第1行,1个数N。(0 <= N <= 500)
第2 - N + 1行:每行N个数,对应矩阵A的元素。(0 <= M[i] <= 16)
第N + 2 - 2N + 1行:每行N个数,对应矩阵B的元素。(0 <= M[i] <= 16)
第2N + 2 - 3N + 1行:每行N个数,对应矩阵C的元素。
Output
如果相等输出Yes,否则输出No。
Input示例
2
1 0
0 1
0 1
1 0
0 1
1 0
Output示例
Yes

 

看到这道题,第一眼:sb题;第二眼:woc要T不可做啊。

然后就去搜了一下,看到第一个题解说什么结合性,恍然大悟。

我们希望把$n^3$的复杂度降到$n^2$。

我们看这个式子:$A \times B = C$

我们可以把他们两边都乘一个矩阵:

$X \times A \times B = X \times C$

如果我们X是一个1*n的矩阵,那么判断这个式子就是$n^2$的。

如果这个式子不成立,那么原式肯定不成立。

我们可以构造多个X来验证。

bzoj1040 矩阵相乘结果的判断

原文:http://www.cnblogs.com/Serene-shixinyi/p/8098894.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!