题意就是求第 n 个斐波那契数。
由于时间和内存限制，显然不能直接暴力解或者打表，想到用矩阵快速幂的做法。
代码如下：
1 #include <cstdio> 2 using namespace std; 3 const int maxn = 100; 4 const int mod = 10000; 5 int a; 6 struct Matrix 7 { 8 int m[maxn][maxn]; 9 }ans,res,w,head; 10 11 Matrix mul(Matrix a,Matrix b,int n) 12 { 13 Matrix tmp; 14 for(int i = 1; i <= n; i++) 15 for(int j = 1; j <= n; j++) 16 tmp.m[i][j] = 0; 17 for(int i = 1; i <= n; i++) 18 for(int j = 1; j <= n; j++) 19 for(int k = 1; k <= n; k++) 20 tmp.m[i][j] += ((a.m[i][k] % mod)*(b.m[k][j] % mod))%mod; 21 return tmp; 22 } 23 24 void quickpow(int N,int n) 25 { 26 for(int i = 1; i <= n; i++) 27 for(int j = 1; j <= n; j++) 28 if(i == j) ans.m[i][j] = 1; 29 else ans.m[i][j] = 0; 30 while(N) 31 { 32 if(N&1) ans = mul(ans,res,2); 33 res = mul(res,res,2); 34 N = N >>1; 35 } 36 } 37 38 int main() 39 { 40 while(scanf("%d",&a)) 41 { 42 if(a == -1) break; 43 else if(a == 0) 44 { 45 puts("0"); 46 continue; 47 } 48 head.m[1][1] = head.m[1][2] = head.m[2][2] = 0; 49 head.m[2][1] = 1; 50 res.m[1][1] = res.m[1][2] = res.m[2][1] = 1; 51 res.m[2][2] = 0; 52 quickpow(a,2); 53 w = mul(ans,head,2); 54 printf("%d ",w.m[1][1]); 55 } 56 return 0; 57 }