poj3070 Fibonacci ——矩阵快速幂

题目大意：

　　求第N项的Fibonacci数的后四位。

题目思路：

　　根据公式：

　　用矩阵快速幂就OK，模板题……但还是TLE了一次，原因是题目要求输入-1结束，我没看到……o(╯□╰)o

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cmath>
 6 using namespace std;
 7 const int MAX = 2;
 8 const int M = 10000;
 9 typedef struct {
10   int m[MAX][MAX];
11 }Matrix;
12 Matrix a, per;
13 int n;
14 void init() {
15   int i , j;
16   for (i = 0; i < n; ++i) {
17     for (j = 0; j < n; ++j) {
18       per.m[i][j] = (i == j);
19     }
20   }
21   a.m[0][0] = a.m[0][1] = a.m[1][0] = 1; a.m[1][1] = 0;
22 }
23 Matrix multi(Matrix a, Matrix b) {
24   Matrix c;
25   int k, i, j;
26   for ( i = 0; i < n; ++i) {
27     for (j = 0; j < n; ++j) {
28       c.m[i][j] = 0;
29       for (k = 0; k < n; ++k) {
30         c.m[i][j] += a.m[i][k] * b.m[k][j];
31       }
32       c.m[i][j] %= M;
33     }
34   }
35   return c;
36 }
37 Matrix power(int k) {
38   Matrix p, ans = per;
39   p = a;
40   while (k) {
41     if (k & 1) {
42       ans = multi(ans, p); k--;
43     }
44     else {
45       k /= 2; p = multi(p, p);
46     }
47   }
48   return ans;
49 }
50 
51 int main(void) {
52   Matrix ans; int k; n = 2;
53   init();
54   while (~scanf("%d", &k)) {
55     if (k == -1) break;
56     init();
57     ans = power(k);
58     printf("%d\n", ans.m[1][0]);
59   }
60   return 0;
61 }

其实就是完完全全的模板……