poj 3070 Fibonacci (矩阵快速幂)

题目大意: 求Fibonacci数列第n项(0 ≤ n ≤ 1,000,000,000)，对m取模后的结果

解题思路: 直接求解第n项，由于n太大，时间复杂度非常高

我们需要构造一个矩阵使得与(a,b)相乘后等于(b,a+b)

不防假设2x2矩阵为:

x1 x2 a b

X =

x3 x4 b a+b

则b=x1*a+x2*b，a+b=x3*a+x4*b

解得: x1=0，x2=1，x3=1，x4=1

同理可得(a,b)*A^n可求出 (数列第n+1项，数列第n+2项)

A^n用矩阵快速幂的思想可以优化为O(log N)

代码:

[cpp]
#include
#include
#include
#define MAX 3
typedef struct node{
int edge[MAX][MAX];
}Matrix;
int n,m=10000;

Matrix map,ant,h;

void Mult(Matrix &a,Matrix &b,Matrix &c) //传递指针,C=A*B
{
int i,j,k;
memset(h.edge,0,sizeof(h.edge));
for(i=0;i<2;i++)
for(j=0;j<2;j++)
for(k=0;k<2;k++)
{
h.edge[i][j]+=a.edge[i][k]*b.edge[k][j]; //***分开写，否则会WA
h.edge[i][j]%=m; //***
}
for(i=0;i<2;i++)
for(j=0;j<2;j++)
c.edge[i][j]=h.edge[i][j];
}

void KSM(Matrix a,int k) //矩阵快速幂
{
while(k>=1)
{
if(k&1) //二进制的思想
Mult(ant,map,ant);
Mult(map,map,map);
k>>=1;
}
}


int main()
{
while(scanf("%d",&n)&&n!=-1)
{
map.edge[0][0]=0; //初始化矩阵
map.edge[0][1]=map.edge[1][0]=map.edge[1][1]=1;
ant.edge[0][0]=1,ant.edge[0][1]=1;
if(n!=0)
{
KSM(ant,n-1); //求第n项，既求 (1,1)*A^(n-1)
printf("%d\n",ant.edge[0][0]);
}
else //第0项为0
printf("0\n");
}
return 0;
}

#include
#include
#include
#define MAX 3
typedef struct node{
int edge[MAX][MAX];
}Matrix;
int n,m=10000;

Matrix map,ant,h;

void Mult(Matrix &a,Matrix &b,Matrix &c) //传递指针,C=A*B
{
int i,j,k;
memset(h.edge,0,sizeof(h.edge));
for(i=0;i<2;i++)
for(j=0;j<2;j++)
for(k=0;k<2;k++)
{
h.edge[i][j]+=a.edge[i][k]*b.edge[k][j]; //***分开写，否则会WA
h.edge[i][j]%=m; //***
}
for(i=0;i<2;i++)
for(j=0;j<2;j++)
c.edge[i][j]=h.edge[i][j];
}

void KSM(Matrix a,int k) //矩阵快速幂
{
while(k>=1)
{
if(k&1) //二进制的思想
Mult(ant,map,ant);
Mult(map,map,map);
k>>=1;
}
}

int main()
{
while(scanf("%d",&n)&&n!=-1)
{
map.edge[0][0]=0; //初始化矩阵
map.edge[0][1]=map.edge[1][0]=map.edge[1][1]=1;
ant.edge[0][0]=1,ant.edge[0][1]=1;
if(n!=0)
{
KSM(ant,n-1); //求第n项，既求 (1,1)*A^(n-1)
printf("%d\n",ant.edge[0][0]);
}
else //第0项为0
printf("0\n");
}
return 0;
}