1 #include <iostream> 2 #include <cstdio> 3 #include <string.h> 4 #include <stdlib.h> 5 #define maxn 5 6 #define MOD 10000 7 using namespace std; 8 class Matrix{ 9 public:10     int row,col;11     __int64 mapp[maxn][maxn];12     Matrix(int r,int c):row(r),col(c){}13     Matrix(){}14     void ini()15     {16         memset(mapp,0,sizeof(mapp));17         mapp[0][0]=mapp[0][1]=mapp[1][0]=1;18     }19     void unit() //单位矩阵的初始化20     {21         memset(mapp,0,sizeof(mapp));22         for(int i=0;i<row;i++)23          mapp[i][i]=1;24     }25     int result() const{return mapp[0][1]%10000;}26     friend Matrix operator*(const Matrix&,const Matrix&);27     void Pow(int);28 };29 Matrix operator*(const Matrix& M1,const Matrix& M2)30 {31     Matrix M(M1.row,M2.col);32     for(int i=0;i<M1.row;i++)33      for(int j=0;j<M2.col;j++)34      {35         M.mapp[i][j]=0;36         for(int k=0;k<M2.col;k++)37          M.mapp[i][j]=(M.mapp[i][j]+M1.mapp[i][k]*M2.mapp[k][j])%MOD;38      }39     return M;40 }41 Matrix M(2,2);42 void Matrix::Pow(int n)//矩阵快速幂43 {44     //cout<<n<<endl;45     Matrix temp(2,2);46     temp.ini();47     while(n)48     {49         if(n&1)50          M=M*temp;51         temp=temp*temp;52         n>>=1;53     }54 }55 int main()56 {57     __int64 n;58     while(scanf("%I64d",&n),n!=-1)59     {60         M.unit();61         if(n==0) cout<<"0"<<endl;62         else if(n==1) cout<<"1"<<endl;63              else64              {65                  Matrix resM(1,2);66                  resM.mapp[0][0]=1,resM.mapp[0][1]=1;67                  M.Pow(n-1);68                  resM=resM*M;69                  cout<<resM.result()<<endl;70              }71     }72     return 0;73 }