学步园

题目链接:    http://poj.org/problem?id=3070

题目大意:    求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)

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#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;
}