HDU 4920 Matrix Multiplication：緩存優化矩陣乘法模 3

題目大意

計算兩個 n×n (n ≤ 800) 矩陣乘積對 3 取模的結果。普通 O(n³) 會超時，需極致優化。

三大優化技巧

1. 迴圈順序調換（緩存友好）：將 k 迴圈提到最外層，改為 i → k → j。這樣 B[k][j] 連續訪問，A[i][k] 在內層迴圈不變，極大減少緩存未命中。
2. 快速輸入：自定義 ReadInt() 直接讀字符並對 3 取模，避免 scanf 開銷。
3. 剪枝：若 A[i][k] == 0 則跳過內層 j 迴圈，因為乘 0 無貢獻。

優化後核心代碼

void Solve() {
    memset(mtRet, 0, sizeof(mtRet));
    for (int i = 1; i <= n; ++i) {
        for (int k = 1; k <= n; ++k) {
            if (!A[i][k]) continue; // 剪枝
            for (int j = 1; j <= n; ++j) {
                mtRet[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}

int ReadInt() {
    int ret = 0; char c;
    while ((c = getchar()) >= '0' && c <= '9')
        ret = ret * 10 + c - '0';
    return ret % 3; // 讀入即取模
}

效果對比

• 無優化：嚴重 TLE
• 僅迴圈調換：通過但較慢
• 三大優化結合：輕鬆 AC，耗時大幅降低

注意：本題利用模 3 特性（數值極小）與 n=800 邊界，使 O(n³) 通過。一般矩陣乘法需 Strassen 或分塊算法。