矩阵乘法和矩阵快速幂

概念

对角矩阵：除了主对角线以外都是 $0$ 的方阵称为对角矩阵。

单位矩阵：主对角线全部是 $1$，其他元素全部是0的方阵。它在乘法里的作用和数学里数字1的作用类似，因此称为单位矩阵。

三角矩阵：主对角线某一侧元素都是 $0$ 的方阵。如果主对角线左下方元素都是 $0$，称为上三角矩阵，否则称为下三角矩阵。

单位三角矩阵：主对角线都是 $1$，且某一侧元素都是0的方阵。

对称矩阵：满足 $a[i][j]=a[j][i]$ 的矩阵称为对称矩阵。常见例子：无向图的邻接矩阵。

矩阵乘幂

定义和数字的乘幂相同，显然只有方阵能这么定义。

既然有乘幂，就自然有快速幂。

快速幂的方法和整数快速幂基本一致。

建议把矩阵给手写一个类，然后用重载运算符和函数的方法来写，会方便很多。

应用：

• 在线性递推中，可以将有用的状态存在一个矩阵中，通过状态矩阵和状态转移矩阵相乘可以得到下一个状态，如果需要做多次这样的重复乘法，那么可以使用快速幂来进行加速。
• 另外就是图论中使用邻接矩阵的一些题目，例如指定边数的路径数量等，也可以用矩阵快速幂优化。

例题

1. 斐波那契第n项

题面

在数列 $\{f_n\}$ 中，$f_1=f_2=1，f_n=f_{n-1}+f_{n-2}$，输入 $n$ 和 $m$，求 $f_n\mod m$。

数据范围：$n\le2\times10^9，m\le10^9+10$。

代码

# include<iostream>
# include<cstring>
using namespace std;

const int mod=1e9+7;
long long n;

struct jz{
	long long a[3][3];
	jz(){
		memset(a,0,sizeof(a));
	}
	void init(){
		for(int i=1;i<=2;++i)
			a[i][i]=1;
	}
}A,B;

jz mul(jz x,jz y){
	jz z;
	for(int i=1;i<=2;++i)
		for(int j=1;j<=2;++j)
			for(int l=1;l<=2;++l)
				z.a[i][j]=(z.a[i][j]+(x.a[i][l]%mod)*(y.a[l][j]%mod)%mod)%mod;
	return z;
}

jz qpow(jz x,long long k){
	jz ans;
	ans.init();
	while(k){
		if(k&1) ans=mul(ans,x);
		x=mul(x,x);
		k>>=1;
	}
	return ans;
}

int main(){
	cin>>n;
	if(n==1){
		cout<<1;
		return 0;
	}
	A.a[1][1]=A.a[1][2]=A.a[2][1]=1;
	B=qpow(A,n-2);
	cout<<(B.a[1][1]+B.a[1][2])%mod;
	return 0;
}

2. 斐波那契前n项和

题面

在数列 $\{f_n\}$ 中，$f_1=f_2=1，f_n=f_{n-1}+f_{n-2}$，令 $S_n=\sum_{k=1}^n f_k$，输入 $n$ 和 $m$，求 $S_n\mod m$。

数据范围：$n\le2\times10^9，m\le10^9+10$。

3. [SCOI2009]迷路

分析

题目给出的实际上就是邻接矩阵。

如果边权只有0和1，那么问题很简单。以前讲过，这种邻接矩阵的k次方的(i,j)元素就是i到j的经过k条边的路径数量，即通过时间为t的路径数量。

所以这个时候直接矩阵快速幂就可以了。

但是本题边权在[0,9]之间。。。咦N≤10啊，直接拆点。

把所有点拆成10个，记(u,x)为u号点拆出来的第x个，我们从所有的(u,x)向(u,x-1)连一条边权为1的有向边，对任何一条从u到v的边权为w的有向边，我们从(u,0)向(v,w-1)连一条边权为1的有向边。这样的话所有边都是0和1且任何(u,0)到(v,0)的路径长度都等于原图中u到v的路径长度。

利用上面的转化，图的结点数不超过100，而且邻接矩阵的边权都是0和1，于是可以直接沿用上面的矩阵快速幂方法即可。

4. [HNOI2008]GT考试

分析

考虑DP。

状态：dp[i][j]表示考虑准考证号的前i位，目前匹配到不吉利数字的第j位的方案总数。

转移方程：dp[i][j]=sum{dp[i-1][p]}，p根据匹配情况的不同而不同。

这样不好优化，我们换个方法写：

dp[i][j]=sum{dp[i-1][k]*g[k][j] | k=0,1,...,m-1}

这里g[k][j]表示一个匹配了长度为k的串，有多少种加数字的方法使得匹配长度变为j。

由于g只和不吉利的数字有关，因此我们可以KMP预处理g数组，在求出next数组后，枚举匹配长度k和前缀ch，暴力计算能匹配到多少的前缀。

然后g这个数组就是一个常量矩阵了，可以用矩阵快速幂来转移dp数组。

作业