poj 3070 Fibonacci

http://poj.org/problem?id=3070
矩阵的快速幂，二分
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 10000
 5 using namespace std;
 6 const int mod=10000;
 7 
 8 int n;
 9 struct node
10 {
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
",m.a[0][1]);
52     }
53     return 0;
54 }
View Code