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 <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; 
} 

#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;
}