大意就是求斐波那契数列第n项，做法为矩阵快速幂。

代码

#include
    
     #include
     
      #include
      
       #define LL long longusing namespace std;const int mod = 10000; struct Mat{    LL a[4][4];    Mat(){        memset(a,0,sizeof(a));    }    Mat operator*(const Mat &h){        Mat c;        for(register int i=1;i<=2;i++)            for(register int j=1;j<=2;j++)                for(register int k=1;k<=2;k++){                    c.a[i][j]+=a[i][k]%mod*h.a[k][j]%mod;                    c.a[i][j]%=mod;                }        return c;    }}ans,f;int n;inline void fast_pow(Mat b,int k){    for(;k;k>>=1){        if(k&1) f=f*b;        b=b*b;    }}int main(){    while(~scanf("%d",&n)){        if(n==-1) break;        f.a[1][1]=0;f.a[1][2]=1;        ans.a[2][1]=ans.a[1][2]=ans.a[2][2]=1;        ans.a[1][1]=0;        fast_pow(ans,n);        printf("%lld\n",f.a[1][1]);    }    return 0;}