HDU 1575 Tr A：矩陣快速冪求跡值

問題描述

給定一個 n×n 方陣 A，要求計算 Tr(A^k) % 9973，其中 Tr 表示矩陣的跡（主對角線元素之和），k 可高達 10^9 量級。

核心思路：矩陣快速冪

直接計算 A^k 不現實，需用二進制快速冪優化：

• A^k = (A^(k/2))^2 （k 為偶數）
• A^k = A × (A^((k-1)/2))^2 （k 為奇數）
• 遞歸深度 O(log k)，每次矩陣乘法 O(n^3)

完整代碼實現

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

typedef long long ll;
const int MOD = 9973;
const int N = 15;

ll k;
int n;

struct Matrix {
    int s[N][N];
    Matrix() { memset(s, 0, sizeof(s)); }
    
    Matrix operator*(const Matrix& other) const {
        Matrix ans;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++)
                    ans.s[i][j] = (ans.s[i][j] + s[i][k] * other.s[k][j]) % MOD;
        return ans;
    }
};

Matrix base;

Matrix pow_mod(ll exp) {
    if (exp == 1) return base;
    Matrix half = pow_mod(exp / 2);
    Matrix ans = half * half;
    if (exp % 2) ans = ans * base;
    return ans;
}

int main() {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d%lld", &n, &k);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &base.s[i][j]);
        
        Matrix result = pow_mod(k);
        int ans = 0;
        for (int i = 0; i < n; i++)
            ans = (ans + result.s[i][i]) % MOD;
        printf("%d\n", ans);
    }
    return 0;
}

優化要點與常見坑

• 模數操作：每次乘法累加後立即取模，防止溢出
• 矩陣結構體：封裝乘法運算符，代碼更清晰
• 遞歸終止條件：exp == 1 直接返回基矩陣
• 長整型：k 可能很大，必須用 long long

矩陣快速冪是解決大指數矩陣運算的標準模板，掌握後可應用於線性遞推、圖論路徑計數等眾多問題。