矩陣乘法 2 (CodeVS 3147) 子矩陣和查詢優化 (前綴和)

問題描述

給兩個 n×n 矩陣 A, B (n ≤ 2000)，m 次查詢 (m ≤ 50000)。每次查詢 C = A×B 中子矩陣 [a..c]×[b..d] 的元素和。矩陣元素 < 100。

關鍵洞察：利用矩陣乘法結合律

C[i][j] = Σₖ A[i][k]·B[k][j]。
子矩陣和 = Σ_{i=a..c} Σ_{j=b..d} Σₖ A[i][k]·B[k][j]
= Σₖ ( Σ_{i=a..c} A[i][k] ) · ( Σ_{j=b..d} B[k][j] )

預處理：
- sumA[i][k] = A 第 k 列前 i 行前綴和。
- sumB[k][j] = B 第 k 行前 j 列前綴和。
則查詢答案 = Σₖ (sumA[c][k]-sumA[a-1][k]) · (sumB[k][d]-sumB[k][b-1])。單次查詢 O(n)。

複雜度

• 預處理：O(n²)
• 每查詢：O(n)
• 總計：O(n² + m·n) ≤ 2000² + 50000×2000 = 1.04×10⁸，C++ 快速 I/O 可過。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
int A[MAXN][MAXN], B[MAXN][MAXN];
long long sumA[MAXN][MAXN], sumB[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m) {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) {
                cin >> A[i][j];
                sumA[i][j] = sumA[i-1][j] + A[i][j];
            }
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) {
                cin >> B[i][j];
                sumB[i][j] = sumB[i][j-1] + B[i][j];
            }
        while (m--) {
            int a,b,c,d; cin >> a >> b >> c >> d;
            if (a > c) swap(a,c);
            if (b > d) swap(b,d);
            long long ans = 0;
            for (int k = 1; k <= n; ++k) {
                long long colSum = sumA[c][k] - sumA[a-1][k];
                long long rowSum = sumB[k][d] - sumB[k][b-1];
                ans += colSum * rowSum;
            }
            cout << ans << '\n';
        }
    }
    return 0;
}

注意

使用 long long 防溢出。輸入量大需關閉同步流並用 cin.tie(nullptr)。