HDU 矩陣快速冪：求 Tr(A^k) % 9973

問題描述

給定 n×n 矩陣 A (n≤10)，求其 k 次冪 (k<10⁹) 的跡（主對角線元素和）模 9973。

矩陣快速冪模板

struct Mat { int a[11][11]; };
Mat mul(Mat A, Mat B) {
    Mat C; memset(C.a, 0, sizeof(C.a));
    for (int i=0; i>= 1;
    }
    return R;
}
int trace(Mat A) {
    int sum = 0;
    for (int i=0; i

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        long long k; scanf("%d%lld", &n, &k);
        Mat M;
        for (int i=0; i