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",an

补充：软件开发 , C++ ,