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;
算法思路：利用快速幂，实现大数范围的快速计算，不会超时
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm> using namespace std;
const int INF = 0x3f3f3f3f; int a[][][];
void test_print(){
for(int i = ; i < ; ++i){
printf("i = %d\n",i);
printf("%d\n\n",a[i][][]);
}
}
int main(){
int i, j, k;
int n;
a[][][] = ;
a[][][] = ;
a[][][] = ;
a[][][] = ;// n = 1 for(i = ; i < ; ++i){
a[i][][] = (a[i-][][] * a[i-][][] + a[i-][][] * a[i-][][]) % ;
a[i][][] = (a[i-][][] * a[i-][][] + a[i-][][] * a[i-][][]) % ;
a[i][][] = (a[i-][][] * a[i-][][] + a[i-][][] * a[i-][][]) % ;
a[i][][] = (a[i-][][] * a[i-][][] + a[i-][][] * a[i-][][]) % ;
}
// test_print();
while(EOF != scanf("%d",&n)){
if(- == n) break;
else if( == n){
printf("0\n");
continue;
}
int count = ;
int flag;
int ans[][];
int array[];
int flag_t = ;
bool init_ok = false;
memset(array, , sizeof(array));
while(n){
if(n % == ){
n /= ;
array[flag_t] = ;
} else{
n = (n - ) / ;
array[flag_t] = ;
}
++flag_t;
}
//for(i = 0; i < flag_t / 2; ++i) swap(array[i], array[flag_t - i -1 ]);
for(i = ; i < flag_t; ++i){
if(!array[i]) continue;
int flag = i;
if(!init_ok){
ans[][] = a[i][][];
ans[][] = a[i][][];
ans[][] = a[i][][];
ans[][] = a[i][][];
init_ok = true;
continue;
}
int temp_1 = ans[][];
int temp_2 = ans[][];
int temp_3 = ans[][];
int temp_4 = ans[][];
ans[][] = (temp_1 * a[flag][][] + temp_2 * a[flag][][]) % ;
ans[][] = (temp_1 * a[flag][][] + temp_2 * a[flag][][]) % ;
ans[][] = (temp_3 * a[flag][][] + temp_4 * a[flag][][]) % ;
ans[][] = (temp_3 * a[flag][][] + temp_4 * a[flag][][]) % ;
}
printf("%d\n",ans[][]);
}
return ;
}