hdu 1575 矩阵快速幂

直接上模板

/*
 * hdu1575/win.cpp
 * Created on: 2011-11-24
 * Author    : ben
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;

/**
 * 矩阵的阶
 */
const int MAX_ORDER = 11;
const int MOD = 9973;

struct MyMatrix {
    int order;
    int num[MAX_ORDER][MAX_ORDER];
    MyMatrix(int ord) {
        order = ord;
    }
    void init() {
        for (int i = 0; i < order; i++) {
            for (int j = 0; j < order; j++) {
                num[i][j] = 0;
            }
        }
    }
};

MyMatrix operator*(MyMatrix ma, MyMatrix mb) {
    int ord = ma.order;
    MyMatrix numc(ord);
    numc.init();
    int i, j, k;
    for (i = 0; i < ord; i++) {
        for (j = 0; j < ord; j++) {
            for (k = 0; k < ord; k++) {
                numc.num[i][j] += ma.num[i][k] * mb.num[k][j];
                numc.num[i][j] %= MOD;
            }
        }
    }
    return numc;
}

MyMatrix mpow(MyMatrix ma, int x) {
    int ord = ma.order;
    MyMatrix numc(ord);
    numc.init();
    for (int i = 0; i < ord; i++) {
        numc.num[i][i] = 1;
    }
    for (; x; x >>= 1) {
        if (x & 1) {
            numc = numc * ma;
        }
        ma = ma * ma;
    }
    return numc;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif
    int T, n, k;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &k);
        MyMatrix tm(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &tm.num[i][j]);
            }
        }
        MyMatrix pm = mpow(tm, k);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += pm.num[i][i];
        }
        printf("%d\n", ans % MOD);
    }
    return 0;
}