矩阵快速幂

#include<iostream>
#include<cstring>
using namespace std;
typedef long long int ll;
int n;
const int mod=10000;
const int text=3;     //矩阵大小
struct node{
    ll a[text][text];

};
node mole(node x,node y){           //矩阵乘
    node sum;
    memset(sum.a,0,sizeof(sum.a));
    for(int i=1;i<text;i++){
        for(int j=1;j<text;j++){
            for(int k=1;k<text;k++){
                sum.a[i][j]+=(x.a[i][k]*y.a[k][j])%mod;
            }
        }
    }
    return sum;
}
node ands(node x,ll y){            //
快速幂
    node sum;
    memset(sum.a,0,sizeof(sum.a));
    for(int i=1;i<text;i++)sum.a[i][i]=1;
    while(y){
        if(y&1)sum=mole(sum,x);
        x=mole(x,x);
        y>>=1;
    }
    return sum;
}
int main(){
    while(cin>>n){
        if(n==-1)break;
        node a1,b1;
        a1.a[1][1]=1;a1.a[1][2]=1;a1.a[2][1]=1;a1.a[2][2]=0;  //斐波那契数列
        b1=ands(a1,n);
        cout<<(b1.a[2][1]+mod)%mod<<endl;
    }
    return 0;
}

b * c = a
a[1][1]=b[1][1]c[1][1]+b[1][2]c[2][1]+b[1][3]c[3][1];
a[1][2]=b[1][1]c[1][2]+b[1][2]c[2][2]+b[1][3]c[3][2];
a[2][1]=b[2][1]c[1][1]+b[2][2]c[2][1]+b[2][3]c[3][1];
a[2][2]=b[2][1]c[1][2]+b[2][2]c[2][2]+b[2][3]c[3][2];