对于普通类型的求a^n，我们的求法是不是a*a*a*a....，这样乘以n次，时间复杂度为O(n)，对于普通n比较小的我们可以接受，然而当n比较大的时候，计算就慢了，所以我们就去寻找更快捷的计算方法！

例如：我们要求2^8，我们通过当为偶数的时候，a^n=(a*a)^(n/2)，当n为奇数时，a^n=a*(a*a)^(n/2)的形式，是不是可以转化为4^4->8^2->64^1，就可以了，2^5的话2*4^2->2*16^1。(把幂化为底数，减少乘法的次数）

int power(int a, int n)//a^n { int ans = 1; while(n > 0) { if(n&1) //当n为奇数时，乘以余下的一个a ans *= a; a *= a; n /= 2; } return ans; }

但是当n比较大时往往我们的结果都非常大，如果直接算的话就会溢出，所以我们在计算的过程中会对结果取模，然后我们就有了快速幂取模算法。控制数据的大小，对于取模我们有(a*b)%c = ((a%c)*(b%c))%c，给出代码。 

int power(long long a, int n) { long long ans = 1; while(n > 0) { if(n&1) { ans *= a; ans %= mod; } a *= a%mod; a %= mod; n /= 2; } return ans%mod; }

下面是矩阵快速幂，区别只是底数换成了矩阵

const int N=10; int n,mod; int temp[N][N]; int res[N][N],a[N][N]; void mul(int a[][N],int b[][N])//矩阵乘法 { memset(temp,0,sizeof(temp)); for(int i=0;i>=1;//幂次/2 } return ; }

应用如下：

我们从最简单的斐波那契数列入手，求菲波那切数列的第n项，n很大，所以MOD1e9+7

斐波的为前两项之和，即发f[0]=1,f[1]=1,f[i] = f[i-1]+f[i-2](i>1)

比较简单的可以直接得到递推式

 

，进一步递推

由于矩阵乘法满足结合律，所它也可以用快速幂算法求解。

然后给一些简单的递推式:
1.f(n)=a*f(n-1)+b*f(n-2)+c；（a,b,c是常数）

2.f(n)=c^n-f(n-1) ；（c是常数）

简单的例子

Fibonacci数列

考虑数列，  
将右边两项看做是一个列向量的形式，令   
很容易得到的形式，即 
现在的任务就是找到一个系数矩阵，使得，且需与无关。 
如果能够找到这个，则易知，于是可以利用矩阵快速幂计算出。这样就可以在的时间内计算出指定的数。 
这个矩阵很容易找，观察易得   

Fibonacci数列变种

推广一下，如果令，则系数矩阵为   

利用二项式展开构造矩阵

计算k次方和

Fibonacci数列只是最简单的例子，对于稍微复杂一点的例子，二项式展开是常用的一项技术。 
考虑计算： 
易得 
如果仿照数列，令 
则 
此时，可求出 
这个系数矩阵很明显是不能用的，因为它与n有关，无法将递推公式转化为矩阵的幂运算。 
这里需要使用二项式展开。 
此时，如果令 
则有 
现在的任务与刚才一样，找到一个系数矩阵，使得，且需与无关。 
有关SnSn的递推公式实际上就指明了AA的最后一行。而利用二项式展开很容易得到其他行。 
有 
最后有 
且 
利用该系数矩阵可以在O(k3logn)O(k3log⁡n)时间内计算出kk次方的和。  

更一般的例子

再考虑一个一般情况：
与刚才几乎一模一样，有 
剩下的步骤，也几乎完全与之前的一样，令 
则 
同样，有关SnSn的递推公式实际上就指明了AA的最后一行，其他行则利用二项式展开得到。 
有   

更复杂的例子

假设要计算如下和式： 
同样，将其写成递推公式，有 
将与有关的项抽出来作为列向量，令 
则  同样，有关Sn的递推公式说明了系数矩阵AA的最后一行。而其他行仍然可以由二项式展开得到，只是相差了一个系数k而已，这很容易解决。 
最后，有