poj 3070 Fibonacci

矩阵快速幂

1 while(N)
2  {
3       if(N&1)
4           res=res*A;
5       n>>=1;
6       A=A*A;
7  }

 1 #include<iostream>
 2 using namespace std;
 3 #deinfe mod 10000
 4 struct matrix
 5 {
 6     int m[2][2];
 7 }ans,base;
 8 matrix multi(matrix a, matrix b)
 9 {
10     matrix t;
11 
12     for(int i = 0; i < 2; i++)
13     {
14         for(int j = 0; j < 2; j++)
15         {
16             t.m[i][j] = 0;
17             for(int pos = 0; pos < 2; pos++)
18             {
19                 t.m[i][j] = (t.m[i][j] + a.m[i][pos] * a[pos][j]) % mod;
20             }
21         }
22     }
23     return t;
24 }
25 int fast(int n)
26 {
27 
28 }
29 
30 int main()
31 {
32     freopen("input.txt","r",stdin);
33     int n;
34     while(scanf("%d",&n) && n != -1)
35     {
36         printf("%d
",fast());
37     }
38     return 0;
39 }