nyoj_148_fibonacci数列(二)_矩阵快速幂

#include <iostream>
#include <cstdio>
#include <cstring>

#define mod 10000

using namespace std;

struct matrix{
    int m[2][2];
};

matrix base,ans;

void init(int n){//只初始化base和ans(单位矩阵)
    memset(base.m,0,sizeof(base.m));
    memset(ans.m,0,sizeof(ans.m));
    for(int i=0;i<2;i++){
        ans.m[i][i]=1;
    }

    base.m[0][0]=base.m[0][1]=base.m[1][0]=1;
}

matrix multi(matrix a,matrix b){
    matrix t;
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            t.m[i][j]=0;
            for(int k=0;k<2;k++){
                t.m[i][j]=(t.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
            }
        }
    }
    return t;
}

int fast_matrix(int n){
    while(n){
        if(n&1){
            ans=multi(ans,base);
        }
        base=multi(base,base);
        n>>=1;
    }
    return ans.m[1][0];
}

int main()
{
    int n;
    while(~scanf("%d",&n) && n!=-1){
        init(n);
        printf("%d\n",fast_matrix(n));
    }
    return 0;
}