简介

矩阵快速幂是一种高效计算矩阵幂的方法。它利用了矩阵的幂运算具有分治性质的特点，可以将矩阵的幂运算时间复杂度从 O(n)降低到 O(logn)。可用于解决线性递推式问题。

---

经典的斐波那契数列fn=fn-1+fn-2。当n很大时，你无法快速的计算第n项的值。可以构造矩阵

 ,   

 

通过矩阵快速幂得到Fn矩阵 a(0,0) 即为 fn 

Code

struct matrix 
{ll mat[2][2];void init() {memset(mat,0,sizeof mat);}
};
matrix mul(matrix a,matrix b)
{matrix c;c.init();for(int i=0;i<2;i++) {for(int j=0;j<2;j++) {for(int k=0;k<2;k++) {c.mat[i][j]+=(a.mat[i][k]%mod)*(b.mat[k][j]%mod)%mod;c.mat[i][j]%=mod;}}}return c;     
}
matrix ksm(matrix a,ll n)
{matrix b;b.init();for(int i=0;i<2;i++) b.mat[i][i]=1;   //单位矩阵while(n){if(n&1) b=mul(b,a);a=mul(a,a);n>>=1;}return b;
}

对于更加复杂的递推式，应灵活构造矩阵来解决

题目

1.求斐波那契数列前n项和

有如下递推式 Fn=Fn-1+Fn-2  Sn=Sn-1+Fn 

构造矩阵

 

2.佳佳的斐波那契

链接：https://www.acwing.com/problem/content/1306/

  

  

附上之前写过的一道矩阵快速幂的题，其实看见题目范围大概就能猜出做法了

强（矩阵快速幂）_Cambrain_的博客-CSDN博客