POJ 3047 Fibonacci

DEBUG很辛苦，且行，且珍惜

原代码：

            ans[0][0] = (ans[0][0]  * a[flag][0][0] + ans[0][1]  * a[flag][1][0]) % 10000;
            ans[0][1] = (ans[0][0]  * a[flag][0][1] + ans[0][1]  * a[flag][1][1]) % 10000;
            ans[1][0] = (ans[1][0] * a[flag][0][0] + ans[1][1]  * a[flag][1][0]) % 10000;
            ans[1][1] = (ans[1][0] * a[flag][0][1] + ans[1][1]  * a[flag][1][1]) % 10000;

问题在于：修改后ans[][]的值再次调用，就不是原来的值了，会导致程序出错

QAQ

改进后：

            ans[0][0] = (temp_1 * a[flag][0][0] + temp_2 * a[flag][1][0]) % 10000;
            ans[0][1] = (temp_1 * a[flag][0][1] + temp_2 * a[flag][1][1]) % 10000;
            ans[1][0] = (temp_3 * a[flag][0][0] + temp_4 * a[flag][1][0]) % 10000;
            ans[1][1] = (temp_3 * a[flag][0][1] + temp_4 * a[flag][1][1]) % 10000;

算法思路：利用快速幂，实现大数范围的快速计算，不会超时

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <iostream>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 const int INF = 0x3f3f3f3f;
 9 
10 int a[40][2][2];
11 void test_print(){
12     for(int i = 0; i < 40; ++i){
13         printf("i = %d
",i);
14         printf("%d

",a[i][0][1]);
15     }
16 }
17 int main(){
18     int i, j, k;
19     int n;
20     a[0][0][0] = 1;
21     a[0][0][1] = 1;
22     a[0][1][0] = 1;
23     a[0][1][1] = 0;// n = 1
24     
25     for(i = 1; i < 40; ++i){
26         a[i][0][0] = (a[i-1][0][0] * a[i-1][0][0] + a[i-1][0][1] * a[i-1][1][0]) % 10000;
27         a[i][0][1] = (a[i-1][0][0] * a[i-1][0][1] + a[i-1][0][1] * a[i-1][1][1]) % 10000;
28         a[i][1][0] = (a[i-1][1][0] * a[i-1][0][0] + a[i-1][1][1] * a[i-1][1][0]) % 10000;
29         a[i][1][1] = (a[i-1][1][0] * a[i-1][0][1] + a[i-1][1][1] * a[i-1][1][1]) % 10000;
30     }
31    // test_print();
32     while(EOF != scanf("%d",&n)){
33         if(-1 == n) break;
34         else if(0 == n){
35             printf("0
");
36             continue;
37         }
38         int count = 0;
39         int flag;
40         int ans[2][2];
41         int array[65];
42         int flag_t = 0;
43         bool init_ok = false;
44         memset(array, 0, sizeof(array));
45         while(n){
46             if(n % 2 == 0){
47                 n /= 2;
48                 array[flag_t] = 0;
49             } else{
50                 n = (n - 1) / 2;
51                 array[flag_t] = 1;
52             }
53             ++flag_t;
54         }
55         //for(i = 0; i < flag_t / 2; ++i) swap(array[i], array[flag_t - i -1 ]);
56         for(i = 0; i < flag_t; ++i){
57             if(!array[i])   continue;
58             int flag = i;
59             if(!init_ok){
60                 ans[0][0] = a[i][0][0];
61                 ans[0][1] = a[i][0][1];
62                 ans[1][0] = a[i][1][0];
63                 ans[1][1] = a[i][1][1];
64                 init_ok = true;
65                 continue;
66             }
67             int temp_1 = ans[0][0];
68             int temp_2 = ans[0][1];
69             int temp_3 = ans[1][0];
70             int temp_4 = ans[1][1];
71             ans[0][0] = (temp_1 * a[flag][0][0] + temp_2 * a[flag][1][0]) % 10000;
72             ans[0][1] = (temp_1 * a[flag][0][1] + temp_2 * a[flag][1][1]) % 10000;
73             ans[1][0] = (temp_3 * a[flag][0][0] + temp_4 * a[flag][1][0]) % 10000;
74             ans[1][1] = (temp_3 * a[flag][0][1] + temp_4 * a[flag][1][1]) % 10000;
75         }
76         printf("%d
",ans[0][1]);
77     }
78     return 0;
79 }