Part I:首先理解一般的快速幂 为快速求a^b，我们可以采用折半的思想： 1:当b为偶数时，a^b = = a^(b/2) * a^(b/2) 2:当b为奇数时，a^b = =a * (a^(b/2)) * (a^(b/2))
代码：
int quick_mi(int a,int b) { int ans=1; while(b) { if(b&1)//奇数隔单,位运算更快，其实还可以写为，b%2==1 { ans=ans*a; } a=a*a;//偶数折半 b=b>>1;//位运算折半，其实还可以写为b=b/2 } return ans; }拓展快速幂取模： 1:根据数学公式:a*b%m=(a%m)*(b%m)%m
代码：
int quick_mi(int a,int b,int c) { int ans=1; while(b) { if(b&1)//奇数隔单 { ans=ans*a%c; } a=a*a%c;//偶数折半 b=b>>1; } return ans; }Part II:矩阵快速幂 1:令MAT为一任意矩阵，求MAT^n: 2:需要定义一个结构体，去方便我们调用矩阵 代码：
struct MATI//定义一个结构体类型，可以定义矩阵 { int a[2][2];//这里我们用最简单的矩阵为例 };3:首先我们需要构造矩阵乘法MAT*MAT 代码：
MATI MX(MATI A,MATI B)//定义矩阵乘法 { MATI C; for(int i=0;i<=2;i++) { for(int j=0;j<2;j++) { for(int k=0;k<2;k++) { C.a[i][j]+=(A.a[i][k]*B.a[k][j]); } } } return C;//返回的矩阵即相乘所得 }4：得到矩阵乘法后，我们模仿快速幂写法即可 代码：
MATI MX_MI(MATI D,int N) { MATI RE; memset(RE.a,0,sizeof(RE.a)); for(int i=0; i<2; i++) RE.a[i][i]=1;//定义初等矩阵 while(N) { if(N&1) RE=MX(RE,D); D=MX(D,D); N=N>>1; } return RE; }提醒： 定义矩阵时候需手动输入值，对于新定义的矩阵需要初始化
矩阵快速幂模板：
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; typedef long long ll; const int mod=1e9+7; const int N=2; ll tmp[N][N],res[N][N]; void multi(ll a[][N],ll b[][N],int n) { memset(tmp,0,sizeof(tmp)); for(ll i=0;i<n;i++) { for(ll j=0;j<n;j++) { for(ll k=0;k<n;k++) { tmp[i][j]+=(a[i][k]*b[k][j])%mod; } tmp[i][j]=tmp[i][j]%mod; } } for(ll i=0;i<n;i++) for(ll j=0;j<n;j++) a[i][j]=tmp[i][j]; } void Pow(ll a[][N],ll m,int n) { memset(res,0,sizeof(res));//m是幂，n是矩阵大小 for(ll i=0;i<n;i++) res[i][i]=1; while(m) { if(m&1) multi(res,a,n);//res=res*a;复制直接在multi里面实现了； multi(a,a,n);//a=a*a m>>=1; } } int main() { ll m; int n; ll a[N][N]; while(~scanf("%lld",&m)) { n=2; a[0][0]=1,a[0][1]=1,a[1][0]=1,a[1][1]=0; Pow(a,m,n); printf("%lld\n",res[1][0]); } return 0; }