先贴一个博主写的，偷个懒先：

快速幂的思路就是：

设A为矩阵，求A的N次方，N很大，1000000左右吧。。。

先看小一点的，A的9次方

A^9

= A*A*A*A*A*A*A*A*A   【一个一个乘，要乘9次】

= A*(A*A)*(A*A)*(A*A)*(A*A) 【保持格式的上下统一，所以加上这句】

 = A*(A^2)^4 【A平方后，再四次方，还要乘上剩下的一个A，要乘6次】

= A*((A^2)^2)^2 【A平方后，再平方，再平方，还要乘上剩下的一个A，要乘4次】

也算是一种二分思想的应用吧，1000000次幂，暴力要乘1000000次，快速幂就只要（log2底1000000的对数） 次，大约20次。。。这。。。我没错吧。。。

但是因为是矩阵，矩阵乘法的复杂度是O(n^3)。。。所以快速幂的复杂度是 

O( (logn)^3 * logn)

上代码！矩阵乘法的代码和上面一样，添加了mat_quick_index(MATRIX a,int N,int n)函数，主函数做了些许修改，以便检验。。。
--------------------- 
作者：番茄鱼片汤 
来源：CSDN 
原文：https://blog.csdn.net/u013795055/article/details/38599321 
版权声明：本文为博主原创文章，转载请附上博文链接！

解释一下：就是说我要求A^9，我不用乘以9次，就好像问2^8=？，ok，我们先算2*2=4；然后就知道2^8=4^4；ok，再算下4*4=16；就知道 2^8=16^2，再算下16*16=256；所以我们算了log8=3次。所以问2^1024次方，不用循环1023次，只要10次ok。

矩阵相乘非常简单自行百度，写成代码不难，这里主要讲下在斐波那契数列之中的运用。

fi[i] = 1*fi[i-1]+1*fi[i-2]

fi[i-1] = 1*f[i-1] + 0*f[i-2];

转换成矩阵形式为：

帮解释一下昂：令  f(n) = {   Fibonacci[n] , Fibonacci[n-1]   } 要求f（5），就相当于求【矩阵】*f( 4 )，然后递归到 {    f（1）,f（0） }；这里在反复乘以矩阵4次了。也就转换成矩阵幂了，如下：

矩阵乘以矩阵的代码很简单，主要讲下这里快速幂的核心代码。

//例如   5->进入if->N=2->N=1->进入if->N=0  结束   E为单位矩阵，N为指数

 while(N>0)
    {
        if(N & 1)  //与运算，即最低位为1即为奇数 执行
            E=mat_multiply(E,a,n);
        N>>=1;     //右移，相当于除以二
        a=mat_multiply(a,a,n);
    }

这里有道斐波那契数列的题目非常经典，emmmm，有时间再补上吧！

http://www.51nod.com/Challenge/Problem.html#!#problemId=1242

千万千万要注意数据类型，我AC提交了四次才过，发现int n 没改 long long n；千万要小心！！！还有一点，是在矩阵乘法里面取模，第一次我在快速幂函数里面取模很多书通不过。知道的欢迎赐教，真心求知，emmm。

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef struct
{
	long long a[2][2];
} matrix;
//矩阵乘法
matrix P(long long a[2][2],long long b[2][2])
{
	matrix c;
	for(int i=0;i<2;i++)
	for(int j=0;j<2;j++)
	c.a[i][j]=0;
	
	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]=(c.a[i][j]+a[i][k]*b[k][j])%1000000009; 
		} 
	} 
	return c;
} 
//矩阵快速幂
matrix Quick(matrix m,long long n)
{
	matrix E;
	for(int i=0;i<2;i++)
	for(int j=0;j<2;j++)
	if(i==j)
	E.a[i][j]=1;
	else
	E.a[i][j]=0;
	
	while(n>0)
	{
		if(n&1)
		E=P(E.a,m.a);
		n>>=1;	
		m=P(m.a,m.a);
		
	}
	return E;
} 
int main()
{
	matrix c,result;
	c.a[1][0]=c.a[0][1]=c.a[0][0]=1;
	c.a[1][1]=0;
	long long n;
	cin>>n;
	result=Quick(c,n-1);
	int fn=result.a[0][0];
	cout<<fn;
	return 0;
} 

然后讲下矩阵快速幂最核心也是最难的部分，构造矩阵：

T * A(n-1)=A(n)，T矩阵就是常数矩阵，而

构建矩阵递推的大致套路,一般An与A(n-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是常数）