【题意】：求Fibonacci数列中的第n项的最后4个数字，不包含前导0。

【题解】：Fibonacci满足以下公式：
                              
               构造矩阵，利用矩阵快速幂求解。

【代码】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 using namespace std;
 5 #define MAX 3
 6 const int MOD = 10000;
 7 struct Mat {
 8     int val[MAX][MAX];
 9     void unit() {
10         for(int i = 0; i < MAX; i++) val[i][i] = 1;
11     }
12     void zero() {
13         memset(val, 0, sizeof(val));
14     }
15 };
16 
17 Mat operator *(const Mat &a, const Mat &b) {
18     Mat tmp;
19     tmp.zero();
20     for(int k = 1; k < MAX; k++) {
21         for(int i = 1; i < MAX; i++) {
22             if(a.val[i][k])
23                 for(int j = 1; j < MAX; j++) {
24                     tmp.val[i][j] += a.val[i][k] * b.val[k][j];
25                     if(tmp.val[i][j] >= MOD) tmp.val[i][j] %= MOD;
26                 }
27         }
28     }
29     return tmp;
30 }
31 
32 Mat operator ^(Mat x, int n) {
33     Mat tmp;
34     tmp.zero(), tmp.unit();
35     while(n) {
36         if(n & 1) tmp = tmp * x;
37         x = x * x;
38         n >>= 1;
39     }
40     return tmp;
41 }
42 
43 int main() {
44     Mat x;
45     int n;
46     x.val[1][1] = x.val[1][2] = x.val[2][1] = 1, x.val[2][2] = 0;
47     while(~scanf("%d", &n)) {
48         if(n == -1) break;
49         Mat ans = x ^ n;
50         printf("%d\n", ans.val[1][2]);
51     }
52     return 0;
53 }
54