POJ3070Fibonacci

矩阵乘法裸题

求快速幂

#include<iostream>
#include<cstdio>
#define ll long long
#define Mod 10000

using namespace std;
struct node
{
    int m[2][2];
}ans,base;

node mul(node a,node b)
{
    node tmp;
    for(int i=0;i<2;i++)
      for(int j=0;j<2;j++)
      {
          tmp.m[i][j]=0;
          for(int k=0;k<2;k++)
          {
              tmp.m[i][j]=(tmp.m[i][j]+a.m[i][k]*b.m[k][j])%Mod;
        }
      }
    return tmp;
}

ll qw(ll n)
{
    base.m[0][0]=1;base.m[0][1]=1;
    base.m[1][0]=1;base.m[1][1]=0;
    ans.m[0][0]=1;ans.m[0][1]=0;
    ans.m[1][0]=0;ans.m[1][1]=1;
    while(n)
    {
        if(n&1) ans=mul(ans,base);
        base=mul(base,base);
        n>>=1;
    }
    return ans.m[0][1];
}

int main()
{
    int n;
    while(scanf("%d",&n)&& n!=-1)
    {   
          printf("%d
",qw(n));
    }
    return 0;
}