转载：快速幂和矩阵快速幂-模板
快速幂的思想就是减少相乘的次数，将原本n-1次的相乘减小到（lg（n））的复杂度；
a^b=(a^2)^(b/2)
这个式子由于/是整除，所以得分奇偶的不同情况，偶数时仍然成立，奇数时需要再乘上一个a；
所以快速幂就是将原本的以a为基本单位的连乘改成以a*a为单位的连乘；
代码：
1 #include 2 #include 3 #include 4 #define ll long long 5 using namespace std; 6 ll quickpow(ll a,ll n,ll mod)//计算的大多是要对mod； 7 { 8 int ans=1; 9 while(n)10 {11 if(n&1)12 ans=ans*a%mod;13 a=a*a%mod;14 b/=2;15 }16 return ans;17 }18 int main()19 {20 int a,b,mod;21 cin>>a>>b>>mod;22 int ans=quickpow(a,b,mod);23 cout<<ans<<endl;24 return 0;25 }矩阵的快速幂是在这个的思想的基础上的，对矩阵进行更新；
题目背景
矩阵快速幂
题目描述给定n*n的矩阵A，求A^k
输入输出格式输入格式：
第一行，n,k
第2至n+1行，每行n个数，第i+1行第j个数表示矩阵第i行第j列的元素
输出格式：
输出A^k
共n行，每行n个数，第i行第j个数表示矩阵第i行第j列的元素，每个元素模10^9+7
输入输出样例输入样例#1：
2 11 11 1
输出样例#1：
1 11 1说明
n<=100, k<=10^12, |矩阵元素|<=1000 算法：矩阵快速幂
代码：
1 #include 2 #define il inline 3 #define ll long long 4 using namespace std; 5 const int mod=1e9+7; 6 ll n,k; 7 struct mat{ll a[102][102],r,c;}; 8 il mat mul(mat x,mat y) 9 {10 mat p;11 memset(&p,0,sizeof(p));12 p.r=x.r,p.c=y.c;13 for(int i=0;����,����i<x.r;i++)14 for(int j=0;j<y.c;j++)15 for(int k=0;k<x.c;k++)16 p.a[i][j]=(p.a[i][j]+x.a[i][k]*y.a[k][j])%mod;17 return p;18 }19 il ll gi()20 {21 ll a=0;char x=getchar();bool f=0;22 while((x<'0'||x>'9')&&x!='-')x=getchar();23 if(x=='-')x=getchar(),f=1;24 while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();25 return f?-a:a;26 }27 int main()28 {29 ios::sync_with_stdio(0);30 n=gi(),k=gi();31 mat p,ans;32 p.r=p.c=ans.r=ans.c=n;33 for(int i=0;i<n;i++)34 for(int j=0;j<n;j++)p.a[i][j]=gi(),ans.a[i][j]=p.a[i][j];35 k--;36 while(k)37 {38 if(k&1)ans=mul(ans,p);39 k>>=1;40 p=mul(p,p);41 }42 for(int i=0;i<n;i++){43 for(int j=0;j<n;j++)cout<<ans.a[i][j]<<' ';44 cout<<endl;45 }46 return 0;47 }
不懂的可以点这里