POJ 3233 矩陣冪級數：最短路徑與矩陣快速冪結合

題目大意

求矩陣級數 S(k) = A + A² + ... + A^k，其中 A 為 n×n 矩陣，結果對 m 取模。直接疊加會超時，需構造增廣矩陣利用快速冪優化。

核心技巧：增廣矩陣

構造 2n × 2n 分塊矩陣：

M = [ A  0 ]
    [ E  E ]   (E 為單位矩陣)

證明可得：

M^k = [ A^k        0     ]
      [ S(k)       E     ]   其中 S(k) = E + A + ... + A^(k-1)

原題求 A + ... + A^k，即計算 S(k+1) 後減去對角線上的 E。

算法流程

1. 讀入 n, k, m 及矩陣 A。
2. 構造增廣矩陣 M（大小 2n），採用向量存儲稀疏矩陣或稠密矩陣均可。
3. 使用矩陣快速冪計算 M^(k+1)，過程中所有乘法對 m 取模。
4. 提取左下 n×n 子矩陣，對角線元素減 1（模 m），即為答案。

關鍵代碼片段 (C++)

using mat = vector>;
mat mul(const mat& a, const mat& b, int mod) {
    int n = a.size();
    mat c(n, vector(n));
    for (int i = 0; i < n; ++i)
        for (int k = 0; k < n; ++k)
            if (a[i][k])
                for (int j = 0; j < n; ++j)
                    c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
    return c;
}
mat pow(mat a, long long e, int mod) {
    int n = a.size();
    mat res(n, vector(n));
    for (int i = 0; i < n; ++i) res[i][i] = 1;
    while (e) {
        if (e & 1) res = mul(res, a, mod);
        a = mul(a, a, mod);
        e >>= 1;
    }
    return res;
}

複雜度分析

• 矩陣乘法：O(n³) 或優化後 O(n²) 視稀疏度。
• 快速冪：O(log k) 次乘法。
• 總體：O(n³ log k) 或更優，滿足 n≤500, m≤100000, k≤10⁹。