#include
     
      #define ll long longusing namespace std;struct matrix{ll g[2][2];};matrix mul(matrix a,matrix b){    matrix c;    c.g[0][0]=c.g[0][1]=c.g[1][0]=c.g[1][1]=0;    for(int i=0;i<=1;i++)    for(int j=0;j<=1;j++)    for(int k=0;k<=1;k++)    c.g[i][j]=(c.g[i][j]+a.g[i][k]*b.g[k][j])%p;    return c;}matrix qpow(matrix a,ll n){    matrix b;    b.g[0][0]=b.g[1][1]=1;    b.g[0][1]=b.g[1][0]=0;    while(n){        if(n&1) b=mul(b,a);        a=mul(a,a);n>>=1;}    return b;}int main(){    ll n;    scanf("%lld",&n);    matrix a;    a.g[0][0]=a.g[0][1]=a.g[1][0]=1;    a.g[1][1]=0;    matrix ans=qpow(a,n);    printf("%lld\n",ans.g[0][1]);return 0;}
     

 矩阵快速幂求斐波那契数列

别人的

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;#define mod 10000struct Matrix{    long long ma[2][2];};Matrix mul(Matrix A,Matrix B){    Matrix C;    C.ma[0][0]=C.ma[0][1]=C.ma[1][0]=C.ma[1][1]=0;    for(int i=0;i<2;i++)    {        for(int j=0;j<2;j++)        {            for(int k=0;k<2;k++)            {                C.ma[i][j]=(C.ma[i][j]+A.ma[i][k]*B.ma[k][j])%mod;            }        }    }    return C;}Matrix pow_mod(Matrix A,long long n){    Matrix B;    B.ma[0][0]=B.ma[1][1]=1;    B.ma[0][1]=B.ma[1][0]=0;    while(n)    {        if(n&1) B=mul(B,A);        A=mul(A,A);        n>>=1;    }    return B;}int main(){    long long n;    while(~scanf("%lld",&n)&&n!=-1)    {        Matrix A;        A.ma[0][0]=1;A.ma[0][1]=1;        A.ma[1][0]=1;A.ma[1][1]=0;        Matrix ans=pow_mod(A,n);        printf("%lld\n",ans.ma[0][1]);    }    return 0;}