[学习笔记]矩阵乘法及其优化dp

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项。斐波那契数列

[TJOI2015]棋盘

矩阵乘法除了这样的优化dp/递推之外,还可以就矩阵乘法本身出一些题目。

以及一些以矩阵乘法为基础的构造

5.板板题——预处理+矩阵+定义新运算

上一篇:forget word qz_c


下一篇:[saiku] olap数据源管理