矩阵快速幂大法

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N=100010,MOD=10000;

int n;
int f[2];

void mul_mat(LL a[][2],LL b[][2])//矩阵乘法
{
    LL c[2][2]={0};
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                c[i][j]=(c[i][j]+a[i][k]*b[k][j]%MOD)%MOD;
    memcpy(a,c,sizeof c);
}

void qmi_mat(LL a[][2],int b)//快速幂
{
    LL res[2][2]{{1,0},{0,1}}; //相当于1
    while(b)
    {
        if(b&1) mul_mat(res,a);
        mul_mat(a,a);
        b>>=1;
    }
    f[0]=res[0][0];
}

int main()
{
    while(cin>>n,n!=-1)
    {
        f[0]=f[1]=1;
        LL a[2][2]={{1,1},{1,0}};
        if(n==0) cout<<0<<endl;
        else 
        {
            qmi_mat(a,n-1);
            cout<<f[0]<<endl;
        }
    }

    return 0;
}