解题思路：
这题的题述是求斐波那契数列的第n个数取模，同时在题干中附上了斐波那契数列的使用矩阵乘的求法。AC代码：
#include#include #include #include using namespace std;struct matrix{long long a[2][2];};matrix c;void mul(matrix a,matrix b){int i,j;for(i=0;i<2;i++) for(j=0;j<2;j++) c.a[i][j]=(a.a[i][0]*b.a[0][j]+a.a[i][1]*b.a[1][j])%10000;}int main(){ matrix ans,fib; long long n,i,j; while(scanf("%lld",&n)!=EOF&&n!=-1){ ans.a[0][0]=1; ans.a[0][1]=1; ans.a[1][0]=1; ans.a[1][1]=0; fib.a[0][0]=1; fib.a[0][1]=0; fib.a[1][0]=0; fib.a[1][1]=1; if(n==0) printf("0\n"); else{ n--; while(n>0){ if(n%2){ mul(ans,fib); fib.a[0][0]=c.a[0][0]; fib.a[0][1]=c.a[0][1]; fib.a[1][0]=c.a[1][0]; fib.a[1][1]=c.a[1][1]; } mul(ans,ans); ans.a[0][0]=c.a[0][0]; ans.a[0][1]=c.a[0][1]; ans.a[1][0]=c.a[1][0]; ans.a[1][1]=c.a[1][1]; n>>=1; } printf("%lld\n",fib.a[0][0]); } } return 0;}