矩阵快速幂基础

    #include<bits/stdc++.h>
    #define db double
    #define ll long long
    #define reg register
    #define pb(x) push_back(x)
    #define fup(i,x,y) for(reg int i=x;i<=y;++i)
    #define fdw(i,x,y) for(reg int i=x;i>=y;--i)
    using namespace std;
    const int mod=10000;
    int n;
    struct wy
    {
        ll a[5][5];
        wy(){memset(a,0,sizeof(a));}
        inline void clear ()
        {
            memset(a,0,sizeof(a));
        }
        wy friend operator *(wy a,wy b) 
        {
            wy c;
            fup(i,1,2) fup(j,1,2) fup(k,1,2) c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%mod;
            return c;
        }
        wy friend operator ^(wy a,ll y)
        {
            wy c;
            fup(i,1,2) c.a[i][i]=1;
            while(y)
            {
                if(y&1) c=c*a;
                y>>=1;
                a=a*a;
             }
             return c;
        } 
    }A,B,C;
    inline int read()
    {
        int x=0,ff=1;
        char ch=getchar();
        while(!isdigit(ch)) {if(ch==‘-‘) ff=-1;ch=getchar();}
        while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
        return x*ff;
    }
    int main()
    {
        freopen("1.in","r",stdin);
        B.a[1][1]=0;B.a[1][2]=1;
        B.a[2][1]=1;B.a[2][2]=1;
        while(1)
        {
            n=read();
            if(n==-1) break;
            if(n<=2) 
            {
                if(n==0) puts("0");
                else puts("1");
                continue;
            }
            A.clear();
            A.a[1][1]=1;A.a[1][2]=1;
            C=B^(n-2);
            A=A*C;
            printf("%lld\n",A.a[1][2]);
        }
        return 0;
    }