HDU 4965 矩陣快速冪優化：從 N×N 到 K×K 的降維技巧

問題背景

給定 N×K 矩陣 A 和 K×N 矩陣 B（元素 0~5），計算 C = A×B（N×N），再求 M = C^N2，最後對每個元素取模 6 求和。N ≤ 1000，K ≤ 6。直接做 N×N 矩陣乘法會超時。

關鍵洞察：結合律降維

利用矩陣乘法結合律：
C^N2 = (A×B)^N2 = A × (B×A)^N2-1 × B

注意 B×A 是 K×K 矩陣（K ≤ 6），對其做快速冪僅需 O(K³ log N)，極快。最後再乘以 A 和 B 還原 N×N 結果。

算法步驟

1. 讀入 A (N×K) 和 B (K×N)。
2. 計算 D = B×A（K×K），每步模 6。
3. 快速冪計算 D^N2-1（模 6）。
4. 計算 E = A×D^N2-1（N×K），模 6。
5. 計算 F = E×B（N×N），模 6，累加所有元素得答案。

複雜度分析

• 矩陣乘法 B×A：O(K²N) ≤ 36×1000 = 3.6×10⁴。
• 快速冪 K×K：O(K³ log N) ≈ 216 × 20 = 4320。
• 後續乘法：O(NK² + N²K) ≈ 1000×36 + 10⁶×6 ≈ 6×10⁶，完全可接受。
• 總體遠快於直接 N×N 矩陣快速冪（O(N³ log N))。

代碼框架（關鍵部分）

struct Matrix {
    int a[10][10];
    Matrix operator*(const Matrix& o) const {
        Matrix r;
        for (int i=0;i>= 1;
    }
    return res;
}

總結

HDU 4965 展示了矩陣乘法結合律在降維中的威力：將大矩陣冪轉化為小矩陣冪，再還原。這類「維度歸約」技巧在矩陣題中極常見，關鍵在於發現 AB 和 BA 的尺寸差異並善用結合律。