51nod1040 矩阵相乘结果的判断
2024-10-08 02:23:24
给出三个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来验证。
最新文章
- 关于jni编译32位、64位动态库(Android.mk和Application.mk文件)
- ZOJ Problem Set - 1216 Deck
- Oracle闪回技术详解
- miniui后台无法接收到input传值
- mybatis05 用户添加
- checkbox复选框全选批量删除
- IOS XMPP
- web端和手机端测试有什么不同
- NOIP2014-普及组复赛-第四题-子矩阵
- 对比requirejs更好的理解seajs
- 搭建Hadoop的环境
- Qt3D
- python网络爬虫&;&;爬取图片
- JMeter上架标的(yyb-csg)
- js Map和Set
- MVC $.Ajax()+Json实现数据库访问并显示数据
- 快速入门:十分钟学会PythonTutorial - Learn Python in 10 minutes
- zookpeer应用和zkclient实践
- java中计算时间差
- She must be at least thirty-five years old.