现在的位置: 首页 > 综合 > 正文

FOJ 1617 Hero’s matrix(矩阵乘法,将3次方复杂度变为二次方)

2018年03月18日 ⁄ 综合 ⁄ 共 311字 ⁄ 字号 评论关闭

转自:http://hi.baidu.com/aekdycoin/item/c325ab8554f113dad1f8cda2

题目:http://acm.fzu.edu.cn/problem.php?pid=1617

给定矩阵A,B,C,验证A*B == C
如果土算,那么乘法的复杂度是o(n^3) 比较是o(n^2)总的来说是o(n^3)
n (1 ≤ n ≤ 500)
土算->TLE
于是考虑,如果A*B=C成立,那么L*(A*B)=L*C,我们知道左边和右边的计算的复杂度是o(n^2)的,可是L的选取也很重要,首先
1.L肯定是一个n维行向量.

2.L中的元素不能全为0.

3.要多选几个L,由于L*(A*B)=L*C成立,A*B=C不一定成立

抱歉!评论已关闭.