在假期里重新回歸算法的學習，首先在這里簡要寫一下利用快速冪來求得斐波那契序列的原理。
具體的代碼和解釋百度里都有涉及，在這里只寫一下自己的推論過程。
由于使用遞歸算法會浪費太多的時間與空間，所以在這里使用矩陣的方法來實現計算。
學過代數的人可以看出，下面這個式子是成立的：
而這個式子可以不斷遞歸，得到下面的式子：
由于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是要取的模
