1.定义:
$c[i][j]=\sum a[i][k]\times b[k][j]$
所以矩阵乘法有条件,(n*m)*(m*p)=n*p
即第一个矩阵的列数等于第二个矩阵的行数,否则没有意义。
2.结合律与分配率
矩阵乘法不一定任何时候都有交换律。因为交换后甚至不能保证第一个矩阵的列数等于第二个矩阵的行数。
但是,矩阵乘法有结合律。
A*B*C=A*(B*C)
这是一个最常用的运算律,使之可以用矩阵快速幂。
3.构造技巧。
矩阵乘法主要用途还是矩阵加速dp。
例如什么n=1e9之类的。
关键还是在于列出dp或者叫递推式子。
BY LYD:
1.一定是线性递推式(斐波那契数列)
2.总有一个转移矩阵(通常还是正方形)一直不变(才能快速幂)
3.矩阵边长不能太大,因为乘法复杂度是O(n^3)
4.矩阵保留能往下递推的项即可。
4.基础应用:
①斐波那契数列第1e9项。斐波那契数列
矩阵乘法除了这样的优化dp/递推之外,还可以就矩阵乘法本身出一些题目。
以及一些以矩阵乘法为基础的构造