poj 3070

算是矩阵快速幂的模板吧
View Code
 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <math.h>
 7 #define N 160
 8 #define mod 10000
 9 #define _clr(a,val) (memset(a,val,sizeof(a)))
10 
11 using namespace std;
12 
13 typedef long long ll;
14 
15 void cal(ll t[][2],ll b[][2])
16 {
17     int c[2][2];
18     _clr(c,0);
19     int i,j,k;
20     for(k = 0; k < 2; k++)
21     {
22         for(i = 0; i < 2; i++)
23         {
24             if(!t[i][k]) continue;
25             for(j = 0; j < 2; j++)
26             {
27                 if(!b[k][j]) continue;
28                 c[i][j] += ((t[i][k] * b[k][j]) % mod);
29             }
30         }
31     }
32     for(i = 0; i < 2; i++)
33     {
34         for(j = 0; j < 2; j++)
35         {
36             c[i][j] %= mod;
37             t[i][j] = c[i][j];
38         }
39     }
40 }
41 void ca(ll a[][2],ll n,ll b[][2])
42 {
43     while(n)
44     {
45         if(n & 1) cal(b,a);
46         cal(a,a);
47         n /= 2;
48     }
49 }
50 int main()
51 {
52     ll n;
53     //freopen("data.txt","r",stdin);
54     while(cin>>n)
55     {
56         if(n < 0) break;
57         if(n == 0 || n == 1)
58         {
59             printf("%d\n",n);
60             continue;
61         }
62         ll a[2][2] = {{0,1},{1,1}};
63         ll b[2][2] = {{1,0},{0,1}};
64         ca(a,n - 1,b);
65         int ans = b[1][1] % mod;
66 
67         printf("%d\n",ans);
68     }
69     return 0;
70 }