题目分析:
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; struct node { int matrix[10][10]; }; node a; node operator * (node x,node y) { node temp; for(int i=0;i<2;i++) for(int j=0;j<2;j++) { int t=0; for(int k=0;k<2;k++) t+=x.matrix[i][k]*y.matrix[k][j]%10000; temp.matrix[i][j]=t%10000; } return temp; } node pow(node x,int k) { node temp;//单位矩阵 temp.matrix[0][0]=temp.matrix[1][1]=1; temp.matrix[0][1]=temp.matrix[1][0]=0; if(k==0) return temp; else if(k==1) return x; else { node t=pow(x,k/2);//开始没注意着,TLE;放到前面有stackflow!!!囧 if(k%2==0) return t*t; else return t*t*x; } } int main() { int n; for(int i=0;i<2;i++) for(int j=0;j<2;j++) { a.matrix[i][j]=1; if(i==1&&j==1) a.matrix[i][j]=0; } while(scanf("%d",&n)!=EOF && n!=-1) { node temp=pow(a,n); int ans=temp.matrix[0][1]; printf("%d\n",ans); } system("pause"); return 0; }