我们将数列写成：
Fibonacci[0] = 0，Fibonacci[1] = 1
Fibonacci[n] = Fibonacci[n-1] + Fibonacci[n-2] (n >= 2)
可以将它写成矩阵乘法形式：
将右边连续的展开就得到：
下面就是要用O(log(n))的算法计算：
代码如下：
/*
求解任一项斐波那契数列值，输入要计算的某一项n，输出该项对应的斐波那契数列值
由于值超大，结果对1000000007取余
*/
#include<iostream>
#include<cstdio>
using namespace std;
struct Matrix
{
__int64 a[2][2];
};
Matrix E;
void InitE(int size) //初始化单位矩阵
{
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
E.a[i][j]=(i==j);
}
}
Matrix MatrixMul(Matrix a,Matrix b) //两矩阵相乘
{
Matrix c;
int i,j,k;
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
c.a[i][j]=0;
for(k=0;k<2;k++)
{
c.a[i][j] += ((a.a[i][k]%1000000007)*(b.a[k][j]%1000000007));
c.a[i][j]%=1000000007;
}
}
}
return c;
}
Matrix MatrixPow(Matrix a,__int64 n) //矩阵快速二分求n次幂
{
Matrix t=E;
while(n>0)
{
if(1&n) //n是奇数
t=MatrixMul(t,a);
a=MatrixMul(a,a);
n >>= 1;
}
return t;
}
int main(void)
{
__int64 n;
Matrix matrix,m;
InitE(2);
while(scanf("%I64d",&n)!=EOF)
{
if(n==1||n==2)
printf("1\n");
else
{
matrix.a[0][0]=1; //构造初始矩阵
matrix.a[0][1]=1;
matrix.a[1][0]=1;
matrix.a[1][1]=0;
m=MatrixPow(matrix,n-1);
printf("%d\n",(m.a[0][0])%1000000007);
}
}
return 0;
}
截图如下：
