题意：
求斐波那契数列，直接矩阵快速幂。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
using namespace std;struct node{int m[2][2];}ans,base;
node cmp(node a, node b){node te;for(int i = 0; i < 2; i++)for(int j = 0; j < 2; j++){te.m[i][j]=0;for(int k = 0; k< 2; k++){te.m[i][j] += a.m[i][k] * b.m[k][j];te.m[i][j] %= 10000; }}return te;
}
int powermod(int n){base.m[0][0] = base.m[0][1] = base.m[1][0] = 1;base.m[1][1] = 0;ans.m[0][0] = ans.m[1][1] = 1;// ans 初始化为单位矩阵ans.m[0][1] = ans.m[1][0] = 0;while(n){if(n&1) ans = cmp(ans, base);n=n/2;base=cmp(base, base);}return ans.m[0][1];}
int main(){int n;while(scanf("%d",&n)&&n != -1){printf("%d\n",powermod(n));}return 0;
}