HDU 4920 Matrix Multiplication (模 3 矩陣乘法優化)

問題

兩個 n×n 矩陣 (n ≤ 800) 相乘，結果模 3。多測試用例，EOF 結束。元素值 ≤ 10⁹。

優化技巧：轉置 + 緩存友好

普通三重循環 O(n³) 會超時。觀察：
C[i][j] = Σₖ A[i][k]·B[k][j]。
若先將 B 轉置為 Bᵀ，則 Bᵀ[j][k] = B[k][j]，內積變為 A[i][k]·Bᵀ[j][k]，內層循環連續訪問內存，大幅提升緩存命中率。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 805;
int A[MAXN][MAXN], B[MAXN][MAXN], C[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) {
                cin >> A[i][j];
                A[i][j] %= 3;
            }
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) {
                cin >> B[j][i]; // 直接讀入轉置
                B[j][i] %= 3;
            }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                int sum = 0;
                for (int k = 1; k <= n; ++k)
                    sum += A[i][k] * B[j][k];
                C[i][j] = sum % 3;
            }
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (j > 1) cout << ' ';
                cout << C[i][j];
            }
            cout << '\n';
        }
    }
    return 0;
}

關鍵點

1. 讀入 B 時直接按列存入實現轉置，無需額外循環。
2. 所有數值提前模 3，避免大數乘積溢出 (int 足夠)。
3. 輸出格式：每行空格分隔，行末換行。

複雜度

O(n³) 但常數極小，n=800 時約 5×10⁸ 次簡單整數運算，C++ O2 優化下 4 秒內可通過。