poj 3070 Fibonacci

先计算幂乘表，根据输入n的二进制位判断是否乘该位相应的幂；

以前做过类似的，但是当时递推矩阵不一样，这次拜读了Ozy的大作，自己敲了一遍；

运行时间： 0ms，神奇吧！

 1 /* poj 3070 */
 2 
 3 # include <stdio.h>
 4 
 5 # define MAXN 30
 6 # define MOD 10000
 7 
 8 short int power[MAXN][4] = {{1,1,1,0}};
 9 short int ans[4];
10 
11 void mul(short int *a, short int *b, short int *c);
12 
13 int main()
14 {
15      int n, i;
16      
17      for (i = 1; i < MAXN; ++i)
18          mul(power[i], power[i-1], power[i-1]);
19      
20      while (~scanf("%d", &n))
21      {
22            ans[0] = ans[3] = 1;
23            ans[1] = ans[2] = 0;
24            if (n == -1) break;
25            for (i = 0; i < MAXN; ++i)
26                  if (n & (0x1<<i)) mul(ans, ans, power[i]);
27            printf("%d\n", ans[1]);
28       }
29      
30      return 0;
31 }
32 
33 void mul(short int *a, short int *b, short int *c)
34 {
35       short int t[4];
36       t[0] = (b[0]*c[0] + b[1]*c[2]) % MOD;
37       t[1] = (b[0]*c[1] + b[1]*c[3]) % MOD;
38       t[2] = (b[2]*c[0] + b[3]*c[2]) % MOD;
39       t[3] = (b[2]*c[1] + b[3]*c[3]) % MOD;
40       memcpy(a, t, sizeof(t));
41 }

/* */