http://poj.org/problem?id=3070

矩阵的快速幂，二分

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #define maxn 10000 5 using namespace std; 6 const int mod=10000; 7  8 int n; 9 struct node10 {11     int a[4][4];12 };13 14 node multi(node s,node t)15 {16     node c;17     for(int i=0; i<2; i++)18     {19         for(int j=0; j<2; j++)20         {21             c.a[i][j]=0;22             for(int k=0; k<2; k++)23             {24                 c.a[i][j]=(c.a[i][j]+s.a[i][k]*t.a[k][j])%mod;25             }26         }27     }28     return c;29 }30 31 32 int main()33 {34     while(scanf("%d",&n)!=EOF)35     {36         if(n==-1) break;37         node m,x;38         m.a[0][0]=1; m.a[0][1]=0;39         m.a[1][0]=0; m.a[1][1]=1;40         x.a[0][0]=x.a[0][1]=x.a[1][0]=1;41         x.a[1][1]=0;;42         while(n)43         {44             if(n&1)45             {46                 m=multi(m,x);47             }48             x=multi(x,x);49             n>>=1;50         }51         printf("%d\n",m.a[0][1]);52     }53     return 0;54 }