首页 > 代码库 > ACM 矩阵题目整理
ACM 矩阵题目整理
先从最基础的矩阵快速幂加速递推开始。
HDU 1005 Number Sequence
|f[n-2],f[n-1]|* |0 B| =|f[n-1], B*f[n-2]+A*f[n-1]|=|f[n-1],f[n]|
|1 A|
建立矩阵如上然后利用快速幂求解即可。答案是mat[0][1]。
#include<iostream>#include<vector>#include<cmath>#include<map>#include<algorithm>#include<cstring>#include<cstdio>#include<cstdlib>#include<queue>#include<cmath>#include<set>#include<string>#define INF 1000000005#define LL long longusing namespace std;const int MAXN =5;struct Matrix{ int n,m; int a[MAXN][MAXN]; void clear(int x=0,int y=0) { n=x; m=y; memset(a,0,sizeof(a)); } Matrix operator * (const Matrix &b)const { Matrix tmp; tmp.clear(n,b.m); for(int i=0; i<n; ++i) for(int j=0; j<b.m; ++j) for(int k=0; k<m; ++k) { tmp.a[i][j]+=a[i][k]*b.a[k][j]; tmp.a[i][j]%=7; } return tmp; }};Matrix quickPow(Matrix mat,int n){ Matrix res; res.clear(2,2); res.a[0][0]=res.a[1][1]=1; while(n) { if(n&1) res=res*mat; mat=mat*mat; n=n>>1; } return res;}int main(){ int A,B,n; while(scanf("%d%d%d",&A,&B,&n)!=EOF) { if(!A&&!B&&!n) break; if(n==1||n==2) { puts("1"); continue; } Matrix mat; mat.clear(2,2); mat.a[0][0]=0; mat.a[0][1]=B; mat.a[1][0]=1; mat.a[1][1]=A; Matrix f; f.clear(1,2); f.a[0][0]=1; f.a[0][1]=1; n-=2; Matrix s=f*quickPow(mat,n); printf("%d\n",(s.a[0][1])%7); } return 0;}
HDU 4920 Matrix multiplication
矩阵乘法，直接算会超时。由于是模3，所以0很多，也就是稀疏矩阵。可以优化。
参见下文：http://www.cnblogs.com/jackiesteed/articles/2021604.html
#include<iostream>#include<vector>#include<map>#include<cmath>#include<algorithm>#include<cstring>#include<cstdio>#include<cstdlib>#include<string>#define LL long longusing namespace std;int A[805][805],B[805][805];int C[805][805];int n;int main(){ int n; while(scanf("%d",&n)!=EOF) { for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) { scanf("%d",&A[i][j]); A[i][j]%=3; } for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) { scanf("%d",&B[i][j]); B[i][j]%=3; } memset(C,0,sizeof(C)); for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) { if(A[i][j]==0) continue; for(int k=1; k<=n; ++k) C[i][k]+=A[i][j]*B[j][k]; } for(int i=1; i<=n; ++i) { for(int j=1; j<=n; ++j) if(j==1) printf("%d",C[i][j]%3); else printf(" %d",C[i][j]%3); printf("\n"); } } return 0;}
HDU 1575 Tr A
求矩阵的迹。直接快速幂即可。
#include<iostream>#include<vector>#include<cmath>#include<map>#include<algorithm>#include<cstring>#include<cstdio>#include<cstdlib>#include<queue>#include<cmath>#include<set>#include<string>#define INF 1000000005#define LL long longusing namespace std;const int MAXN =12;struct Matrix{ int n,m; int a[MAXN][MAXN]; void clear(int x=0,int y=0) { n=x; m=y; memset(a,0,sizeof(a)); } Matrix operator * (const Matrix &b)const { Matrix tmp; tmp.clear(n,b.m); for(int i=0; i<n; ++i) for(int j=0; j<b.m; ++j) { for(int k=0; k<b.m; ++k) { if(0==a[i][j]) continue;//优化！ tmp.a[i][k]+=a[i][j]*b.a[j][k]; tmp.a[i][k]%=9973; } } return tmp; } void setOne(int x) { clear(x,x); for(int i=0; i<x; ++i) a[i][i]=1; }};Matrix one;Matrix quickPow(Matrix mat,int n){ Matrix res=one; while(n) { if(n&1) res=res*mat; mat=mat*mat; n=n>>1; } return res;}int main(){ int T; scanf("%d",&T); while(T--){ int n,k; scanf("%d%d",&n,&k); one.setOne(n); Matrix mat; mat.clear(n,n); for(int i=0;i<n;++i) for(int j=0;j<n;++j) scanf("%d",&mat.a[i][j]); mat=quickPow(mat,k); int ans=0; for(int i=0;i<n;++i) { ans+=mat.a[i][i]; ans%=9973; } printf("%d\n",ans); } return 0;}
HDU 1757 A Simple Math Problem
一个简单的递推，建立矩阵后，快速幂。
#include<iostream>#include<vector>#include<cmath>#include<map>#include<algorithm>#include<cstring>#include<cstdio>#include<cstdlib>#include<queue>#include<cmath>#include<set>#include<string>#define INF 1000000005#define LL long longusing namespace std;const int MAXN =12;int M;struct Matrix{ int n,m; int a[MAXN][MAXN]; void clear(int x=0,int y=0) { n=x; m=y; memset(a,0,sizeof(a)); } Matrix operator * (const Matrix &b)const { Matrix tmp; tmp.clear(n,b.m); for(int i=0; i<n; ++i) for(int j=0; j<b.m; ++j) { for(int k=0; k<b.m; ++k) { if(0==a[i][j]) continue;//优化！ tmp.a[i][k]+=a[i][j]*b.a[j][k]; tmp.a[i][k]%=M; } } return tmp; } void setOne(int x) { clear(x,x); for(int i=0; i<x; ++i) a[i][i]=1; }};Matrix one;Matrix quickPow(Matrix mat,int n){ Matrix res=one; while(n) { if(n&1) res=res*mat; mat=mat*mat; n=n>>1; } return res;}int main(){ int k; one.setOne(10); while(scanf("%d%d",&k,&M)!=EOF) { Matrix mat; mat.clear(10,10); for(int i=0; i<9; ++i) mat.a[i+1][i]=1; for(int i=0; i<10; ++i) scanf("%d",&mat.a[9-i][9]); if(k<10) printf("%d\n",k%M); else { Matrix f; f.clear(1,10); for(int i=0; i<10; ++i) f.a[0][i]=i; k-=9; f=f*quickPow(mat,k); printf("%d\n",f.a[0][9]); } } return 0;}
UVa 10870 Recurrences
与上面类型相似的题，建立矩阵，再快速幂加速。注意会超int。
#include<iostream>#include<vector>#include<cmath>#include<map>#include<algorithm>#include<cstring>#include<cstdio>#include<cstdlib>#include<queue>#include<cmath>#include<set>#include<string>#define INF 1000000005#define LL long longusing namespace std;const int MAXN =20;int M;struct Matrix{ int n,m; LL a[MAXN][MAXN]; void clear(int x=0,int y=0) { n=x; m=y; memset(a,0,sizeof(a)); } Matrix operator * (const Matrix &b)const { Matrix tmp; tmp.clear(n,b.m); for(int i=0; i<n; ++i) for(int j=0; j<b.m; ++j) { for(int k=0; k<b.m; ++k) { if(0==a[i][j]) continue;//优化！ tmp.a[i][k]+=a[i][j]*b.a[j][k]; tmp.a[i][k]%=M; } } return tmp; } void setOne(int x) { clear(x,x); for(int i=0; i<x; ++i) a[i][i]=1; }};Matrix one;Matrix quickPow(Matrix mat,LL n){ Matrix res=one; while(n) { if(n&1) res=res*mat; mat=mat*mat; n=n>>1; } return res;}int main(){ int d,n; while(scanf("%d%d%d",&d,&n,&M)!=EOF) { if(!d&&!n&&!M) break; one.setOne(d); Matrix mat; mat.clear(d,d); for(int i=0; i<d; ++i) mat.a[i+1][i]=1; for(int i=0; i<d; ++i) scanf("%lld",&mat.a[d-1-i][d-1]); Matrix f; f.clear(1,d); for(int i=0; i<d; ++i) scanf("%lld",&f.a[0][i]); if(n<=d) printf("%lld\n",f.a[0][n-1]%M); else { n-=d; f=f*quickPow(mat,n); printf("%lld\n",f.a[0][d-1]%M); } } return 0;}
POJ 3734 Blocks
递推+矩阵快速幂。
设计状态的时候要考虑所有可能的情况，保证无重复无遗漏，再考虑转移。最后用矩阵加速。
#include<iostream>#include<vector>#include<cmath>#include<map>#include<algorithm>#include<cstring>#include<cstdio>#include<cstdlib>#include<queue>#include<cmath>#include<set>#include<string>#define INF 1000000005#define LL long longusing namespace std;const int MAXN =4;int M=10007;struct Matrix{ int n,m; int a[MAXN][MAXN]; Matrix(int x=0,int y=0):n(x),m(y) { memset(a,0,sizeof(a)); } void clear(int x=0,int y=0) { n=x; m=y; memset(a,0,sizeof(a)); } Matrix operator * (const Matrix &b)const { Matrix tmp; tmp.clear(n,b.m); for(int i=0; i<n; ++i) for(int j=0; j<b.m; ++j) { for(int k=0; k<b.m; ++k) { if(0==a[i][j]) continue;//ÓÅ»¯£¡ tmp.a[i][k]+=a[i][j]*b.a[j][k]; tmp.a[i][k]%=M; } } return tmp; } void setOne(int x) { clear(x,x); for(int i=0; i<x; ++i) a[i][i]=1; }};Matrix one;Matrix quickPow(Matrix mat,int n){ Matrix res=one; while(n) { if(n&1) res=res*mat; mat=mat*mat; n=n>>1; } return res;}int main(){ one.setOne(3); int T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); Matrix mat(3,3); mat.a[0][0]=2,mat.a[0][1]=1,mat.a[0][2]=0; mat.a[1][0]=2,mat.a[1][1]=2,mat.a[1][2]=2; mat.a[2][0]=0,mat.a[2][1]=1,mat.a[2][2]=2; Matrix f(3,1); f.a[0][0]=1; Matrix ans=f*quickPow(mat,n); printf("%d\n",ans.a[0][0]); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。