矩阵快速幂

本文主要是介绍矩阵快速幂，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

板子

题目

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define maxn 110
#define ll long long
using namespace std;
template<typename T>
inline void read(T &x){
	x=0;bool flag=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
	for(;isdigit(c);c=getchar()) x=x*10+(c^48);
	if(flag) x=-x;
}

const int mod=1e9+7;
ll n,k;

struct Matrix{
	int m,n;
	ll a[maxn][maxn];
	
	inline void init(int _m=0,int _n=0){
		m=_m;n=_n;
		memset(a,0,sizeof a);
	}
    
    inline Matrix operator + (Matrix B){
		Matrix res;
        res.init(m,n);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                res.a[i][j]=a[i][j]+B.a[i][j];
        return res;
    }
    
    inline Matrix operator - (Matrix B){
		Matrix res;
        res.init(m,n);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                res.a[i][j]=(a[i][j]-B.a[i][j]+mod)%mod;
        return res;
    }
    
    inline Matrix operator * (int c){
		Matrix res;
        res.init(m,n);
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
                res.a[i][j]=c*a[i][j];
        return res;
    }
	
	inline Matrix operator * (Matrix B){
		Matrix res;
		res.init(m,B.n);
		for(int i=1;i<=m;i++)
			for(int j=1;j<=B.n;j++)
				for(int k=1;k<=n;k++)
					(res.a[i][j]+=a[i][k]*B.a[k][j])%=mod;
		return res;
	}
	
	inline void id(){
		for(int i=1;i<=n;i++) a[i][i]=1;
	}
	
	inline Matrix qpow(ll t){
		Matrix res;
		res.init(m,m);
		res.id();
		Matrix tmp=*this;
		for(;t;t>>=1,tmp=tmp*tmp) if(t&1) res=res*tmp;
		return res;
	}

};

int main(){
	read(n),read(k);
	Matrix s,ans;
	s.init(n,n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			read(s.a[i][j]);
	ans=s.qpow(k);
	for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            printf("%lld ",ans.a[i][j]);
        }
        cout<<endl;
    }
	return 0;
}

例题

Lougu P1939矩阵加速

题目

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define int long long//不开long long的话会爆int 
using namespace std;

const int mod=1e9+7;
int t,n;

struct matrix{
    int a[4][4];
    matrix(){
        memset(a,0,sizeof(a));
    }
    inline void build(){
        for(int i=1;i<=3;i++) a[i][i]=1;
    }
    matrix friend operator * (matrix x,matrix y){
        matrix res;
        for(int i=1;i<=3;i++)
            for(int j=1;j<=3;j++)
                for(int k=1;k<=3;k++)
                    (res.a[i][j]+=x.a[i][k]*y.a[k][j]%mod)%=mod;
        return res;
    }
};

inline matrix qpow(matrix a,int t){
    matrix res;
    res.build(); 
    for(;t;t>>=1,a=a*a)
        if(t&1) res=res*a;
    return res;
}

signed main(){
    cin>>t;
    for(int i=1;i<=t;i++){
        cin>>n;
        if(n<=3){
            cout<<1<<endl;
            continue;
        }
        matrix s;
        memset(s.a,0,sizeof(s.a));
        s.a[1][1]=s.a[1][2]=s.a[2][3]=s.a[3][1]=1;
        s=qpow(s,n-2);
        cout<<(s.a[1][1]+s.a[1][3])%mod<<endl;
    }
    return 0;
}

Luogu P1962斐波那契数列

题目

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string.h>
#define ll long long
using namespace std;
const int mod=1e9+7;

ll n;

struct Matrix{
    ll m,n;
    ll a[3][3];
    Matrix(){
        memset(a,0,sizeof(a));
    }
    inline void build(){
        for(int i=1;i<=2;i++) a[i][i]=1;
    }
    Matrix friend operator * (Matrix x,Matrix y){
        Matrix res;
        for(int i=1;i<=2;i++)
            for(int j=1;j<=2;j++)
                for(int k=1;k<=2;k++)
                    (res.a[i][j]+=x.a[i][k]*y.a[k][j]%mod)%=mod;
        return res;
    }
    
};

inline Matrix qpow(Matrix a,ll t){
    Matrix res;
    res.build();
    for(;t;t>>=1,a=a*a)
        if(t&1) res=res*a;
    return res;
}

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

Luogu P1707刷题比赛

题目

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 20
#define ll long long
using namespace std;
template<typename T>
inline void read(T &x){
	x=0;bool flag=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
	for(;isdigit(c);c=getchar()) x=x*10+(c^48);
	if(flag) x=-x;
}

ll n,mod,p,q,r,t,u,v,w,x,y,z;

ll qmul(ll a, ll b) {
	ll res = 0;
	for(; b; b >>= 1, a = (a << 1) % mod) if(b & 1) res = (res + a) % mod;
	return res;
}

struct Matrix {
	int m, n;
	ll a[N][N];
	void init(int _m, int _n) {
		m = _m, n = _n;
		memset(a, 0, sizeof(a));
	}
	Matrix operator * (Matrix B) {
		Matrix res;
		res.init(m, B.n);
		for(int i = 1; i <= m; i ++)
			for(int j = 1; j <= B.n; j ++)
				for(int k = 1; k <= n; k ++)
					res.a[i][j] = (res.a[i][j] + qmul(a[i][k], B.a[k][j])) % mod;
		return res;
	}
	void id() {
		for(int i = 1; i <= m; i ++)
			a[i][i] = 1;
	}
	Matrix fpow(ll k) {
		Matrix res, tmp = *this;
		res.init(m, n);
		res.id();
		for(; k; k >>= 1, tmp = tmp * tmp) if(k & 1) res = res * tmp;
		return res;
	}
};

int main() {
	read(n),read(mod);
	read(p),read(q),read(r),read(t);
    read(u),read(v),read(w);
    read(x),read(y),read(z);
	if(n<=2){
		printf("nodgd %d\n",n==2?3:1);
		printf("Ciocio %d\n",n==2?3:1);
		printf("Nicole %d",n==2?3:1);
		return 0;
	} 
	else n-=2;
	ll s[N*N]={
		p, q, 1, 0, 1, 0, r, 2*r+t, r+t+1, 0, 0,
		1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		1, 0, u, v, 1, 0, 0, 0, 0, w, 0,
		0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
		1, 0, 1, 0, x, y, 0, 1, 3, 0, z,
		0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 1, 2, 1, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, w, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, z,
		3, 1, 3, 1, 3, 1, 0, 0, 1, 1, 1
	};
	Matrix op,ans;
	op.init(11,11);ans.init(11,1);
	int cnt=0;
	for(int i=1;i<=11;i++)
		for(int j=1;j<=11;j++)
			op.a[i][j]=s[cnt++];
	for(int i=1;i<=11;i++) ans.a[i][1]=s[cnt++];
	op=op.fpow(n);
	op=op*ans;
	cout<<"nodgd "<<op.a[1][1]<<endl;
    cout<<"Ciocio "<<op.a[3][1]<<endl;
    cout<<"Nicole "<<op.a[5][1]<<endl;
	return 0;
}

Luogu P1397矩阵游戏

题目

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define maxn 1000010
#define ll long long
using namespace std;
template<typename T>
inline void read(T &x){
    x=0;bool flag=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
    for(;isdigit(c);c=getchar()) x=x*10+(c^48);
    if(flag) x=-x;
}

const int mod=1e9+7;
ll a,b,c,d;
char n[maxn],m[maxn];

ll md(ll x){
	return x>mod?x-mod:x;
}

struct Matrix{
    ll s[3][3];
    Matrix(){
        memset(s,0,sizeof(s));
    }
    inline void build(){
        for(int i=1;i<=2;i++) s[i][i]=1;
    }
}m1,m2;

Matrix operator * (Matrix x,Matrix y){
    Matrix res;
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            for(int k=1;k<=2;k++)
            	res.s[i][j]=md(res.s[i][j]+(x.s[i][k]*y.s[k][j])%mod);
    return res;
}

inline Matrix qpow_(Matrix a,ll b){
	Matrix res;
	res.build();
	for(;b;b>>=1,a=a*a) if(b&1) res=res*a;
	return res;
}

inline Matrix qpow(Matrix a,char *b){
	int x=strlen(b)-1;
    Matrix res;
    res.build();
    for(int i=x;i>=0;i--){
    	res=res*qpow_(a,b[i]-'0');
    	a=qpow_(a,10);
    }
    return res;
}

void pre(){
    m1.s[1][1]=a,m1.s[1][2]=b,m1.s[2][1]=0,m1.s[2][2]=1;
    m2.s[1][1]=c,m2.s[1][2]=d,m2.s[2][1]=0,m2.s[2][2]=1;
}

int main(){
    scanf("%s",&n);scanf("%s",&m);
    ll lenn=strlen(n)-1,lenm=strlen(m)-1;
    for(int i=lenn;i>=0;i--){
        if(n[i]=='0') n[i]='9';
        else {n[i]=n[i]-1; break;}
    }
    for(int i=lenm;i>=0;i--){
        if(m[i]=='0') m[i]='9';
        else {m[i]=m[i]-1; break;}
    }
    read(a),read(b),read(c),read(d);
    pre();
    m1=qpow(m1,m);
    m2=m2*m1;
    m2=m1*qpow(m2,n);
    ll ans=md(m2.s[1][1]+m2.s[1][2]);
    cout<<ans<<endl;
    return 0;
}//gaojing

Luogu P3758可乐

题目

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define maxn 110
using namespace std;
template<typename T>
inline void read(T &x){
	x=0;bool flag=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
	for(;isdigit(c);c=getchar()) x=x*10+(c^48);
	if(flag) x=-x;
}

const int mod=2017;
int n,m,u,v,t;
int ans;

struct Matrix {
	int m, n;
	int a[maxn][maxn];

	void init(int _m, int _n) {
		m = _m, n = _n;
		memset(a, 0, sizeof(a));
	}

	Matrix operator * (Matrix B) {
		Matrix res;
		res.init(m, B.n);
		for(int i = 1; i <= m; i ++)
			for(int j = 1; j <= B.n; j ++)
				for(int k = 1; k <= n; k ++)
					res.a[i][j] = (res.a[i][j] + (a[i][k] * B.a[k][j])%mod) % mod;
		return res;
	}

	void build() {
		for(int i = 1; i <= m; i ++) a[i][i] = 1;
	}

//	Matrix qpow(int k) {
//		Matrix res, tmp = *this;
//		res.init(m, m);
//		res.build();
//		for(; k; k >>= 1, tmp = tmp * tmp) if(k & 1) res = res * tmp;
//		return res;
//	}
};

inline Matrix qpow(Matrix &a,int b){
	Matrix res;
	res.init(n,n);
	res.build();
	for(;b;b>>=1,a=a*a) if(b&1) res=res*a;
	return res;
}

int main(){
	Matrix s;
    read(n),read(m);
    s.init(n+1,n+1);
    for(int i=1;i<=m;i++){
        read(u),read(v);
        s.a[u][v]=1;s.a[v][u]=1;
    }
    read(t);
    for(int i=1;i<=n+1;i++) s.a[i][i]=1;
    for(int i=1;i<=n+1;i++) s.a[i][n+1]=1;
    Matrix tot=qpow(s,t);
//    (int i=1;i<=n;i++){
//    	for(int j=1;j<=n;j++) cout<<s.a[i][j]<<" ";
//    	cout<<endl;
//    }
    for(int i=1;i<=n+1;i++) ans=(ans+tot.a[1][i])%mod;
    cout<<ans<<endl;
    return 0;
}

Luogu P4159迷路

题目

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define maxn 110
#define ll int
using namespace std;
template<typename T>
inline void read(T &x){
	x=0;bool flag=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
	for(;isdigit(c);c=getchar()) x=x*10+(c^48);
	if(flag) x=-x;
}

const int mod=2009;
int n,t,nn;
char c[15];

int check(int a,int b){
	return 9*(a-1)+b;
}

struct Matrix{
	ll m,n;
	ll a[maxn][maxn];
	
	inline void init(int _m=0,int _n=0){
		m=_m,n=_n;
		memset(a,0,sizeof(a));
	}

	inline void build(){
		for(int i=1;i<=m;i++) a[i][i]=1;
	}
	
	Matrix operator * (Matrix B){
		Matrix res;
		res.init(m,B.n);
		for(int i=1;i<=m;i++)
			for(int j=1;j<=B.m;j++)
				for(int k=1;k<=n;k++)
					res.a[i][j]=(res.a[i][j]+(a[i][k]*B.a[k][j])%mod)%mod;
		return res;
	}
	
};

inline Matrix qpow(Matrix &a,ll b){
	Matrix res;
	res.init(n,n);
	res.build();
	for(;b;b>>=1,a=a*a) if(b&1) res=res*a;
	return res;
}

int main(){
    cin>>n>>t;
    nn=9*n;
    Matrix s;
    s.init(nn,nn);
//    cout<<1<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=8;j++){
            s.a[check(i,j)][check(i,j+1)]=1;
        }
//        cout<<2<<endl;
        for(int j=1;j<=n;j++){
            cin>>c[j];
            if(c[j]!='0') s.a[check(i,c[j]-'0')][check(j,1)]=1;
        }
    }
    s=qpow(s,t);
    cout<<s.a[1][9*n-8]%mod<<endl;
    return 0;
}

Luogu P2579沼泽鳄鱼

题目

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#define maxn 60
using namespace std;
template<typename T>
inline void read(T &x){
    x=0;bool flag=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
    for(;isdigit(c);c=getchar()) x=x*10+(c^48);
    if(flag) x=-x;
}

const int mod=10000;
int n,m,st,en,k,nfish,x,y;
int r,rr[maxn];

struct Matrix{
	int m,n;
	int a[maxn][maxn];
	
	inline void init(int _m=0,int _n=0){
		m=_m;n=_n;
		memset(a,0,sizeof a);
	}
	
	inline void build(){
		for(int i=0;i<m;i++) a[i][i]=1;
	}
	
	inline Matrix operator * (Matrix B){
		Matrix res;
		res.init(m,B.n);
		for(int i=0;i<m;i++)
			for(int j=0;j<B.m;j++)
				for(int k=0;k<n;k++)
					(res.a[i][j]+=a[i][k]*B.a[k][j]%mod)%=mod;
		return res;
	}
	
	inline Matrix fpow(int t){
		Matrix res;
		res.init(m,m);
		res.build();
		Matrix tmp=*this;
		for(;t;t>>=1,tmp=tmp*tmp) if(t&1) res=res*tmp;
		return res;
	}
};

Matrix B,T[13],S;
vector<int> s;

int main(){
	read(n),read(m),read(st),read(en),read(k);
	B.init(n,n);
	for(int i=1;i<=m;i++){
		read(x),read(y);
		B.a[x][y]=1;
		B.a[y][x]=1;
	}
	for(int i=1;i<=12;i++) T[i]=B;
	read(nfish);
	for(int i=1;i<=nfish;i++){ 
		read(r);
		for(int j=0;j<r;j++) read(rr[j]);
		rr[r]=rr[0];
		for(int j=1;j<=12;j++)
			for(int g=0;g<n;g++)
				T[j].a[g][rr[(j-1)%r+1]]=0;
	}
	T[0].init(n,n);
	T[0].build();
	for(int i=1;i<=12;i++) T[0]=T[0]*T[i];
	S=T[0].fpow(k/12);
	k=k%12;
	for(int i=1;i<=k;i++) S=S*T[i];
	cout<<S.a[st][en];
	return 0;
}

Luogu P2233公交车路线

题目
~~其实是应该用矩阵的但是既然有好写的递推可以拿来水题那为什么不呢~~
贴一个巨好写的递推：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define maxn 20
#define ll long long
using namespace std;
template<typename T>
inline void read(T &x){
	x=0;bool flag=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
	for(;isdigit(c);c=getchar()) x=x*10+(c^48);
	if(flag) x=-x;
}

const int mod=1000;
ll n;
ll ans=0,b=1;

int main(){
    read(n);
    if(n%2) {
        cout<<0<<endl;
        return 0;
    }
    for(int i=1;i<=n/2-1;i++){
        ans=2*ans+b;
        b+=ans;
        ans%=1000;b%=1000;
    }
    (ans*=2)%=1000;
    cout<<ans<<endl;
    return 0;
}

再贴一个矩乘正解：(来自线代神仙wsy_jim)

#include<bits/stdc++.h>
using namespace std;
const int N=10,Mod=1000;



struct Matrix{
	int m,n;
	int a[N][N];
	
	inline void init(int _m=0,int _n=0){
		m=_m;n=_n;
		memset(a,0,sizeof a);
	}
	
	inline Matrix operator * (Matrix B){
		Matrix res;
		res.init(m,B.n);
		for(int i=1;i<=m;i++)
			for(int j=1;j<=B.m;j++)
				for(int k=1;k<=n;k++)
					(res.a[i][j]+=a[i][k]*B.a[k][j])%=Mod;
		return res;
	}
	
	inline void id(){
		for(int i=1;i<=m;i++) a[i][i]=1;
	}
	
	inline Matrix fpow(int t){
		Matrix res;
		res.init(m,m);
		res.id();
		Matrix tmp=*this;
		for(;t;t>>=1,tmp=tmp*tmp) if(t&1) res=res*tmp;
		return res;
	}
};

int n;

int main(){
	
	cin>>n;
	
	if(n<=3){cout<<0;return 0;}
	if(n==4){cout<<2;return 0;}
	
	Matrix x;
	x.init(8,8);
	x.a[1][2]=x.a[1][8]=x.a[2][1]=x.a[2][3]=x.a[3][2]=x.a[3][4]=x.a[4][3]=1;
	x.a[4][5]=x.a[6][5]=x.a[6][7]=x.a[7][6]=x.a[7][8]=x.a[8][1]=x.a[8][7]=1;
	
	cout<<x.fpow(n).a[1][5];
	
	return 0;
}

再贴一个奇怪的DP：(来自Blueqwq）

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+10;
const int mod=1000;
inline int read(){
	int x=0;bool f=false;char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')	f=true;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return f?-x:x;
}
int n;
int f[2][10];
int main(){
	n=read();
	if(n&1){
		puts("0");
		return 0;
	}
	f[0][1]=1;
	for(int i=1;i<=n;i++){
		memset(f[i&1],0,sizeof f[i&1]);
		for(int j=1;j<=8;j++){
			if(j-1!=5) f[i&1][j]+=f[(i&1)^1][(j-1==0?8:j-1)];
			if(j+1!=5) f[i&1][j]+=f[(i&1)^1][(j+1==9?1:j+1)];
			f[i&1][j]%=mod;
		}
	} 
	printf("%d",f[n&1][5]);
	return 0;
}

这篇关于矩阵快速幂的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

矩阵快速幂

板子

例题

Lougu P1939矩阵加速

Luogu P1962斐波那契数列

Luogu P1707刷题比赛

Luogu P1397矩阵游戏

Luogu P3758可乐

Luogu P4159迷路

Luogu P2579沼泽鳄鱼

Luogu P2233公交车路线

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯