矩阵专题小结

转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

做了几个矩阵问题，总结一下。

矩阵是个很神奇的东西，有时候对于一个有规律的操作，需要执行很多次的时候，有时候可以构造矩阵很巧妙的解决。

另外对于递推式求解，可以通过构造矩阵巧妙解决。

经典的便是FIB数列，以及FIB数列的求和问题。

HDU 1575 Tr A

http://acm.hdu.edu.cn/showproblem.php?pid=1575

赤裸的矩阵快速幂乘

#include<iostream>#include<cstring>#include<queue>#include<cstdio>#include<cmath>#include<algorithm>#define N 10#define inf 1<<29#define MOD 9973#define LL long longusing namespace std;struct Matrix{int m[N][N];}init;int n,k;Matrix Mult(Matrix m1,Matrix m2){Matrix ans;for(int i=0;i<n;i++)for(int j=0;j<n;j++){ans.m[i][j]=0;for(int k=0;k<n;k++)ans.m[i][j]=(ans.m[i][j]+m1.m[i][k]*m2.m[k][j])%MOD;}return ans;}Matrix Pow(Matrix m1,int b){Matrix ans;for(int i=0;i<n;i++)for(int j=0;j<n;j++)ans.m[i][j]=(i==j);while(b){if(b&1)ans=Mult(ans,m1);m1=Mult(m1,m1);b>>=1;}return ans;}int main(){int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&k);for(int i=0;i<n;i++)for(int j=0;j<n;j++)scanf("%d",&init.m[i][j]);init=Pow(init,k);int ans=0;for(int i=0;i<n;i++)ans=(ans+init.m[i][i])%MOD;printf("%d\n",ans);}return 0;}

http://acm.hdu.edu.cn/showproblem.php?pid=1588

构造矩阵，通过矩阵乘法可以得到FIB数列的某一项，矩阵为{1,1,1,0}
其中这里要求的为
F(b)+F(k+b)+F(2*k+b)……
用矩阵表示即为A^b+A^(k+b)……，可以转化为A^b*(A^(0)+A^(k)……)
将K=A^k,即A^b*(K^0+K^1+K^2……)，对于括号内部部分，有经典的二分解法，在Matrix67博客里面也有介绍

#include<iostream>#include<cstring>#include<queue>#include<cstdio>#include<cmath>#include<algorithm>#define N 2using namespace std;struct Matrix{int m[N][N];}init,unit;int n=2;int MOD;Matrix Mult(Matrix m1,Matrix m2){Matrix ans;memset(ans.m,0,sizeof(ans.m));for(int i=0;i<n;i++)for(int k=0;k<n;k++){if(m1.m[i][k])    for(int j=0;j<n;j++) ans.m[i][j]=(ans.m[i][j]+(m1.m[i][k]*m2.m[k][j]))%MOD;}return ans;}Matrix Pow(Matrix m1,int b){Matrix ans;for(int i=0;i<n;i++)for(int j=0;j<n;j++)ans.m[i][j]=(i==j);while(b){if(b&1)ans=Mult(ans,m1);m1=Mult(m1,m1);b>>=1;}return ans;}int main(){int t,k;scanf("%d",&t);while(t--){scanf("%d%d",&k,&MOD);if(k==0){printf("0\n");continue;}init.m[0][0]=init.m[0][1]=init.m[1][0]=1;init.m[1][1]=0;init=Pow(init,2*k-1);printf("%d\n",init.m[0][0]);}return 0;}




Re: ACM_cxlove47分钟前
回复lywh348977787n多谢!