在假期里重新回归算法的学习，首先在这里简要写一下利用快速幂来求得斐波那契序列的原理。
具体的代码和解释百度里都有涉及，在这里只写一下自己的推论过程。
由于使用递归算法会浪费太多的时间与空间，所以在这里使用矩阵的方法来实现计算。
学过代数的人可以看出，下面这个式子是成立的：
而这个式子可以不断递归，得到下面的式子：
由于Fib[0]与Fib[1]是已知，那么只需求矩阵的次幂就可以了。
在这里使用到的就是快速幂，关于快速幂的解释看这里：
http://baike.baidu.com/link?url=dbyx1Lo9P_Ca2cRdKuttAobLhFrmlyfGuCYn1MnzHvOVu-QwilkS3guqyxSZNXIWxlW8s9IIPAgf2_swv093Hq
简单来说就是 使用位运算来快速求得一个数的 多少个次幂。
简单的位运算有&，|，<<，>>，~，^等，具体使用方法不再赘述。
在这里使用的是快速幂的非递归算法。
当求一个数a的n次幂的时候，需要将该数a相乘n次，那么时间复杂度为n，为了减小该时间复杂度，需要减小n。
已知任意一个数k都可以写成2n0+2n1+2^n2……形式，那么有：
假设n=11，那么:
我们想要求a的11次幂，只需将11的2进制数从低位开始取，每次取一位，将该位数乘2的相应位数（从一开始取位累加）次幂，将a取该数的次幂再累乘即可。
在这里截取网上的相关代码：
int Qpow(int a,int n)
{
int ans = 1;
while(n)
{
if(n&1) ans *= a;
a *= a;
n >>= 1;
}
return ans;
}
而斐波那契数列的求取需要求的是一个矩阵的幂，故需要将函数中的所有乘法替换为22矩阵的乘法，然后将a与ans均替换为22的矩阵，矩阵相乘的函数可根据代数知识获得：
matrix multi(matrix a, matrix b)//matrix是2*2的矩阵类
{
matrix tmp;
for(int i = 0; i < 2; ++i)
{
for(int j = 0; j < 2; ++j)
{
tmp.m[i][j] = 0;
for(int k = 0; k < 2; ++k)
tmp.m[i][j] = (tmp.m[i][j] + a.m[i][k] * b.m[k][j]) ;
}
}
return tmp;
}
替换后的快速幂函数表示为：
int fast_mod(int n) //a与ans都是2*2的矩阵类型：matrix
{
a.m[0][0] =a.m[0][1] = a.m[1][0] = 1;
a.m[1][1] = 0; //初始矩阵的值
ans.m[0][0] = ans.m[1][1] = 1; // ans 初始化为单位矩阵
ans.m[0][1] = ans.m[1][0] = 0;
while(n)
{
if(n & 1)
ans = multi(ans, a);
a = multi(a, a);
n >>= 1;
}
return ans.m[0][1];
}
如果需要求某个斐波那契数取数b的模，那么根据代数知识，矩阵的每个数都需要求得该数的模，且每次相乘都需取模，则在矩阵相乘的函数中每次相乘后取一次模即可。
位置代码如下：
for(int k = 0; k < 2; ++k)
tmp.m[i][j] = (tmp.m[i][j] + a.m[i][k] * b.m[k][j]) % b;//b是要取的模
