从 NOIOnline#3T2 谈矩阵快速幂及其优化

1 矩阵快速幂优化数列递推

我们来看最基础的斐波那契数列: $f_n=f_{n-1}+f_{n-2}$。

暴力做是$O(n)$的我们可以设计矩阵来优化——设计一个初始矩阵$A$表示数列的初值，然后再设计一个矩阵$B$使得每次初始矩阵乘上其之后都会变成下一个状态。

一般转移有几步就会设多大的矩阵。

比如一个斐波那契数列的转移，我们可以都早这样一个$A$：

1 1

0 0

再构造这样一个$B$：

1 1

1 0

我们发现$A \times B$即为：

2 1

0 0

这里补充一下矩阵的乘法：对于答案矩阵$C$，有$C[i][j]=\sum_{k=1}^{N}A[i][k] \times B[k][j]$

可是这样有什么用呢？

应为矩阵的乘法也满足交换律和结合律，所以也可以用快速幂来优化乘法。

比如我们要求一个递推数列的第$M$项，这个数列的递推式有$N$项，则我们可以在$O(N^3 \times \log{M})$的时间复杂度内求得。

例题：数列

Code：AC记录

2 矩阵快速幂优化dp

很多dp题都是递推数列，所以就可以用矩阵快速幂来做。

比如这道：zyd的妹子其二

很容易退出最暴力的dp方程：$dp[i][j] += dp[i-1][k], (j, k不排斥)$其中$dp[i][j]$代表前i个第i个选第j种妹子的方案数。

但是这题m很小，n甚大，所以直接暴力推是会TLE的。

很显然这是个递推数列（从状态i-1推到i），所以我们可以用矩阵乘法来优化。

我们把所有排斥的部分设为0，其余设为1然后做矩阵乘法即可。

Code：AC记录

3 图上的矩阵快速幂

我们最开始学存图的时候肯定都是用邻接矩阵存的，矩阵，矩阵！！！

所以图上一个点能到的点就构成一个矩阵结构。

例题：（NOI online3# T2）魔法值（矩阵快速幂只能拿暴力的40pts，可以先尝试写一下）

4 一些很妙的优化

1 常数优化

如果将做矩阵乘法时的代码改成k在j前循环，则内存的访问是连续的，可以有一点优化效果（虽然大部分时候是用不到的）。

2 一些玄学优化、

照刚刚的思想，我们发现如果$A[i][k]=0$则最后一步j的循环时不需要的，可以直接continue。

这样做看似没有什么大作用，其实很有用。

因为原本的的$A$矩阵大部分时间其实是个向量，也就是用$A \times B$的时间只是$O(N^2)$。

3 倍增处理B矩阵

针对多组数据。

如果把B矩阵先用倍增处理好，然后对于每一个查询都直接用A矩阵乘上那些处理好的矩阵则复杂度变为$O(N^2 \log{M})$。

可以过掉上面的例题：AC代码

5 和其它算法混用

例题：GT考试（kmp+dp+矩阵快速幂优化）

Code：AC代码

习题：可乐（请读者自己思考）

从 NOIOnline#3T2 谈矩阵快速幂及其优化

原文：https://www.cnblogs.com/zcr-blog/p/12953467.html