矩阵

1.矩阵快速幂

struct matrix{ll mat[N][N];}a;
matrix operator *(const matrix &a,const matrix &b){
	matrix c;
	memset(c.mat,0,sizeof(c.mat));
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			for(int k=0;k<N;k++){
				c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%MOD;
			}
		}
	}
	return c;
}
matrix quickPow(matrix a,ll n){
	matrix ans;
	memset(ans.mat,0,sizeof(ans.mat));
	for(int i=0;i<N;i++)ans.mat[i][i]=1;
	while(n){
		if(n&1)ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}

2.矩阵快速幂加速递推

例题：poj3070

求Fn，n<=2^63

去求矩阵的幂

最终左下角的数就是Fn

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int MOD = 1e4;
struct matrix{long long m[3][3];};
matrix mul(matrix a,matrix b,int n){
	matrix C;
	memset(C.m,0,sizeof(C.m));
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			int r=a.m[i][k];
			for(int j=1;j<=n;j++){
				C.m[i][j]+=r*b.m[k][j];
				C.m[i][j]%=MOD;
			}
		}
	}
	return C;
} 
matrix quickPow(matrix A,int n,int k){
	matrix C;
	memset(C.m,0,sizeof(C.m));
	for(int i=1;i<=n;i++)C.m[i][i]=1;
	while(k){
		if(k&1)C=mul(C,A,2);
		A=mul(A,A,2);
		k>>=1;
	}
	return C;
}
int main(){
	long long n;
	while(cin>>n&&~n){
		matrix A;
		if(n==0||n==1||n==2){
			printf("%d\n",n==0?0:1);
			continue;
		}
		A.m[1][1]=0;
		A.m[1][2]=A.m[2][1]=A.m[2][2]=1;
		A=quickPow(A,2,n-1);
		cout<<A.m[2][2]<<'\n';
	}
	return 0;
}

3.矩阵乘法和路径问题

例题：poj3613

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 120,INF = 0x3f;
int Hash[N*10],cnt=0;
struct matrix{int m[N][N];};
matrix operator *(const matrix& a,const matrix& b){
	matrix c;memset(c.m,INF,sizeof(c.m));
	for(int i=1;i<=cnt;i++){
		for(int j=1;j<=cnt;j++){
			for(int k=1;k<=cnt;k++){
				c.m[i][j]=min(c.m[i][j],a.m[i][k]+b.m[k][j]);
			}
		}
	}
	return c;
}
matrix quickPow(matrix a,int n){
	matrix ans=a;
	--n;
	while(n){
		if(n&1)ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,t,s,e;cin>>n>>t>>s>>e;
	matrix a;memset(a.m,INF,sizeof(a.m));
	while(t--){
		int u,v,w;cin>>w>>u>>v;
		if(!Hash[u])Hash[u]=++cnt;
		if(!Hash[v])Hash[v]=++cnt;
		a.m[Hash[u]][Hash[v]]=a.m[Hash[v]][Hash[u]]=w;
	}
	matrix ans=quickPow(a,n);
	cout<<ans.m[Hash[s]][Hash[e]];
	return 0;
}