【概述】

矩阵快速幂利用矩阵的乘法与整数快速幂的结合，能够快速的算出 n 阶方阵 A 的 M 次幂 A^b，其结果仍是一个矩阵，无具体含义，在信息学竞赛中，矩阵快速幂常用于求解线性递推关系。

关于矩阵的基础知识：点击这里

关于线性递推关系：点击这里

【n*m 矩阵的快速幂】

struct Matrix{LL s[N][N]; }; Matrix e;//单位矩阵E Matrix x;//构造矩阵 void init(int n){for(int i=1;i<=n;i++)//主对角线为1e.s[i][i]=1; } Matrix mul(Matrix A,Matrix B,LL n){//矩阵乘法，n代表A、B两个矩阵是n阶方阵Matrix temp;//临时矩阵，存放A*B结果for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)temp.s[i][j]=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)temp.s[i][j]=((temp.s[i][j]+A.s[i][k]*B.s[k][j])%MOD+MOD)%MOD;return temp; } Matrix quickPower(Matrix a,LL b,LL n){//矩阵快速幂，求n阶矩阵a的b次幂Matrix ans=e;while(b){if(b&1)ans=mul(ans,a,n);//ans=e*aa=mul(a,a,n);//a=a*ab>>=1;}return ans; } int main(){LL n,m; //构造矩阵的大小、阶scanf("%lld%lld",&n,&m);init(n);//单位矩阵初始化for(int i=1;i<=n;i++)//输入构造矩阵，也可通过题目的递推公式来构造矩阵for(int j=1;j<=n;j++)cin>>x.s[i][j];Matrix res=quickPower(x,m,n);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)printf("%lld ",res.s[i][j]);printf("\n");}return 0; }

【1*n 矩阵的快速幂】 

struct Matrix{LL s[N];//1*n的矩阵 }; Matrix e;//单位矩阵E Matrix x;//构造矩阵x void init(int n){//单位矩阵的第一行for(int i=1;i<=n;i++)e.s[i]=0;e.s[1]=1; } Matrix mul(Matrix A,Matrix B,LL n){//矩阵乘法Matrix temp;//临时矩阵，存放矩阵A*矩阵B的结果for(int i=1;i<=n;i++)temp.s[i]=0;for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)temp.s[i]=(temp.s[i]+(A.s[j]*B.s[i-j+1])%MOD)%MOD;return temp; } Matrix quickPower(Matrix A,LL k,LL n){//矩阵快速幂Matrix res=e;while(k){if(k&1)res=mul(A,res,n);//res=A*eA=mul(A,A,n);//A=A*Ak>>=1;}return res; } int main(){LL n,k;scanf("%lld%lld",&n,&k);init(n);for(int i=1;i<=n;i++)//构造矩阵初始值，根据题目要求推导x.s[i]=1;Matrix res=quickPower(x,k,n);//k次幂for(int i=1;i<=n;i++)printf("%d ",res.s[i]);printf("\n");return 0; }

【矩阵 1~k 次幂的和】

原理：二分求和

• 当 n 是奇数时：
• 当 n 是偶数时：

struct Matrix{LL s[N][N]; }; Matrix add(Matrix A,Matrix B){//A+BMatrix temp;for(int i=0;i<n;i++)for(int j=0;j<n;j++)temp.s[i][j]=(A.s[i][j]+B.s[i][j])%mod;return temp; } Matrix sum(Matrix A,int k){//A+A^2+A^3+…+A^kif(k==1)return A;if(k%2){Matrix temp=sum(A,k-1);Matrix pow=quickPow(A,k);return add(temp,pow);}else {Matrix temp=sum(A,k>>1);Matrix pow=add(quickPow(A,k>>1),E);return mul(temp,pow);} }

【经典问题：共轭矩阵的构造】

1.问题

对于给出的 a、b、m、n，当满足  时，求：

2.思路

设 ，配项 ，并令 

由于 An、Bn 恰好共轭，因此 An、Bn 的和与积均为有理数

根据  ，可知 Bn<1

因此 ，那么 

故而可根据 Cn 来构造共轭矩阵，进行矩阵快速幂来求 Sn

3.共轭式的构造

根据  构造共轭矩阵

对 Cn 两端同乘 ，有：

进行化简：

写成矩阵形式：

再递推一步：

其中，

然后根据构造的矩阵进行矩阵快速幂计算结果即可

【例题】

Fast Matrix Calculation（HDU-4965）(矩阵化简)：点击这里

So Easy!（HDU - 4565）(共轭矩阵的构造)：点击这里

Partial Sums（CF-223B）(1*n 的矩阵快速幂)：点击这里

总结

以上是生活随笔为你收集整理的线性代数 —— 矩阵快速幂的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。