C++ – POJ-3070 矩阵快速幂

#include <cstdio>
#include <cstring>
using namespace std;
const int MOD = 1e4;
const int MAXN = 12;
struct Mat {
    long long mat[MAXN][MAXN];
    int n, m;
    Mat operator * (const Mat &b) const {
        Mat a = *this;
        Mat ans;
        ans.n = a.n;
        ans.m = b.m;
        memset(ans.mat, 0, sizeof ans.mat);
        for(int i = 0; i < ans.n; i++) 
            for(int j = 0; j < ans.m; j++) 
                for(int k = 0; k < a.m; k++) 
                    ans.mat[i][j] += a.mat[i][k] * b.mat[k][j], ans.mat[i][j] %= MOD;
        return ans;
    }
    Mat qpow(int k) {
        Mat ans;
        ans.n = n;
        ans.m = m;
        for(int i = 0; i < ans.n; i++) {
            for(int j = 0; j < ans.m; j++) {
                ans.mat[i][j] = (i == j);
            }
        }
        while(k) {
            if(k & 1)
                ans = ans * *this;
            *this = *this * *this;
            k >>= 1;
        }
        return ans;
    }
};
long long qpow(long long a, long long n) {
    long long re = 1;
    while(n) {
        if(n & 1) re = (re * a) % MOD;
        a = (a * a) % MOD;
        n >>= 1;
    }
    return re % MOD;
}
int main() {
    while(true) {
        long long a;
        scanf("%lld", &a);
        if(a == -1) break;
        Mat te;
        te.m = te.n = 2;
        te.mat[0][0] = 1, te.mat[0][1] = 1;
        te.mat[1][0] = 1, te.mat[1][1] = 0;
        te = te.qpow(a);
        Mat ta;
        ta.n = 2;
        ta.m = 1;
        ta.mat[0][0] = 0;
        ta.mat[1][0] = 1;
        ta = te * ta;
        printf("%lld\n", ta.mat[0][0]);
    }

    return 0;
}