Hiểu bài toán

Bài toán yêu cầu tính tích của hai ma trận A (kích thước n x p) và B (kích thước p x m). Kết quả là một ma trận C (kích thước n x m), trong đó mỗi phần tử C[i][j] bằng tổng tích của các phần tử tương ứng của hàng thứ i ma trận A và cột thứ j ma trận B: C[i][j] = sum(A[i][k] * B[k][j]) cho k từ 0 đến p-1. Do giá trị có thể rất lớn, yêu cầu lấy dư của kết quả cho 10^9 + 7. Các phần tử đầu vào có thể âm nên cần xử lý lấy dư đúng cách để luôn trả về số không âm trong khoảng [0, MOD-1].

Các cách tiếp cận

Cách Naive Matrix Multiplication

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long a[505][505];
long long b[505][505];
long long c[505][505];
int main() {
    int n, p, m;
    cin >> n >> p >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < p; j++)
            cin >> a[i][j];
    for(int i = 0; i < p; i++)
        for(int j = 0; j < m; j++)
            cin >> b[i][j];
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            long long sum = 0;
            for(int k = 0; k < p; k++) {
                sum = (sum + (a[i][k] % MOD) * (b[k][j] % MOD)) % MOD;
            }
            // Handle negative result
            c[i][j] = (sum + MOD) % MOD;
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++)
            cout << c[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

• Time Complexity: O(n * p * m)
• Space Complexity: O(n * p + p * m + n * m)

Đây là cách tiếp cận trực tiếp nhất để nhân ma trận. Ta sử dụng 3 vòng lặp lồng nhau: vòng ngoài cùng duyệt qua các hàng của ma trận A (i), vòng giữa duyệt qua các cột của ma trận B (j), và vòng trong cùng tính toán tổng tích tương ứng (k). Với mỗi phần tử C[i][j], ta tính tổng các tích A[i][k] * B[k][j] cho k từ 0 đến p-1. Ta phải chú ý lấy dư modulo 10^9 +7 sau mỗi phép nhân và cộng để tránh tràn số. Vì giá trị đầu vào có thể âm, ta cần chuẩn hóa kết quả cuối cùng về dạng không âm bằng cách lấy (value % MOD + MOD) % MOD.

Cách Optimized Naive (Modulo Handling)

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long a[505][505];
long long b[505][505];
long long c[505][505];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, p, m;
    cin >> n >> p >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < p; j++){
            cin >> a[i][j];
            a[i][j] %= MOD;
            if (a[i][j] < 0) a[i][j] += MOD;
        }
    }
    for(int i = 0; i < p; i++){
        for (int j = 0; j < m; j++){
            cin >> b[i][j];
            b[i][j] %= MOD;
            if(b[i][j] < 0) b[i][j] += MOD;
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            long long sum = 0;
            for(int k = 0; k < p; k++){
                long long mul = (a[i][k] * b[k][j]) % MOD;
                sum += mul;
                if (sum >= MOD) sum -= MOD;
            }
            c[i][j] = sum;
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cout << c[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

• Time Complexity: O(n * p * m)
• Space Complexity: O(n * p + p * m + n * m)

Phương pháp này giống với cách tiếp cận Naive nhưng tối ưu hóa việc xử lý số học modulo. Thay vì thực hiện phép chia lấy dư (modulo) sau mỗi phép cộng (thao tác chậm), ta nhập các giá trị đầu vào vào ma trận A và B ngay lập tức về dạng không âm trong khoảng [0, MOD-1]. Trong vòng lặp tính toán, phép nhân được thực hiện và lấy dư, sau đó cộng vào biến tổng. Thay vì dùng phép chia (%) để kiểm tra tràn, ta sử dụng phép trừ (-) vì tổng chắc chắn chỉ chênh lệch một số MOD. Sử dụng ios::sync_with_stdio(false) và cin.tie(nullptr) giúp tăng tốc độ nhập xuất.

Cách Struct-based Implementation

#include <bits/stdc++.h>
#define ll long long
const int MOD = 1e9 + 7;
using namespace std;
ll n, p, m;
struct matrix {
    vector<vector<ll>> val;
    matrix(ll a, ll b) {
        val.resize(a + 1, vector<ll>(b + 1, 0));
    }
    matrix() {}
};
matrix nhan(matrix a, matrix b) {
    matrix c(a.val.size() - 1, b.val[0].size() - 1);
    for(int i = 1; i < a.val.size(); i++)
        for(int j = 1; j < b.val[0].size(); j++) {
            c.val[i][j] = 0;
            for(int k = 1; k < a.val[0].size(); k++)
                c.val[i][j] = (c.val[i][j] + a.val[i][k] * b.val[k][j]) % MOD;
            c.val[i][j] = (c.val[i][j] % MOD + MOD) % MOD;
        }
    return c;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> p >> m;
    matrix a(n, p);
    matrix b(p, m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= p; j++)
            cin >> a.val[i][j];
    for(int i = 1; i <= p; i++)
        for(int j = 1; j <= m; j++)
            cin >> b.val[i][j];
    matrix c = nhan(a, b);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++)
            cout << c.val[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

• Time Complexity: O(n * p * m)
• Space Complexity: O(n * p + p * m + n * m)

Cách tiếp cận này sử dụng cấu trúc (struct) matrix để đóng gói dữ liệu ma trận, giúp code trở nên rõ ràng và dễ quản lý hơn, đặc biệt là trong các bài toán yêu cầu các thao tác ma trận phức tạp hơn. Logic tính toán vẫn là nhân ma trận ba vòng lặp cơ bản. Dữ liệu được lưu trữ trong vector<vector<ll>>. Việc lấy dư được xử lý bằng (c.val[i][j] % MOD + MOD) % MOD để đảm bảo kết quả luôn dương.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Cần phải lấy dư modulo 10^9 + 7 cho cả phép nhân và phép cộng để tránh tràn số nguyên 64-bit, vì giá trị tích có thể lên tới ~10^18 (vượt quá giới hạn của số nguyên 32-bit nhưng vẫn trong giới hạn của long long 64-bit, nhưng khi cộng dồn nhiều thì sẽ tràn).
• Vì các phần tử đầu vào có thể âm, ta cần chuẩn hóa kết quả sau khi lấy dư. Phép chia lấy dư trong C++ với số âm có thể trả về số âm. Công thức chuẩn hóa là (x % MOD + MOD) % MOD.

Lỗi thường gặp

• Quên xử lý số âm: Nếu input chứa số âm và ta chỉ thực hiện sum % MOD, kết quả có thể bị in ra số âm.
• Tràn số khi tính toán: Nếu không lấy dư ở mỗi bước nhân hoặc cộng, biến sum có thể vượt quá giới hạn của long long (khoảng 9e18), dẫn đến sai lệch kết quả.
• Tối ưu hóa truy cập bộ nhớ: Việc truy cập ma trận theo thứ tự hàng (row-major) trong C++ giúp tận dụng cache tốt hơn. Trong nhân ma trận chuẩn, vòng lặp trong cùng (k) truy cập b[k][j] theo cột, có thể gây giảm hiệu năng (cache miss) trên các ma trận lớn. Tuy nhiên với n, p, m <= 500, độ phức tạp thuật toán O(500^3) đã là ~1.25e8, đủ để chạy trong thời gian cho phép (thường là 1s) với C++ optimized.