Hiểu bài toán

Bài toán yêu cầu tính tổng ba vòng lặp: $$\sum_{i=1}^{A} \sum_{j=1}^{B} \sum_{k=1}^{C} ijk$$ và in ra kết quả sau khi chia lấy phần dư cho $998244353$. Với $A, B, C$ lên tới $10^9$ và $T$ (số test case) lên tới $10^5$, chúng ta cần một công thức toán học có độ phức tạp $O(1)$ cho mỗi test case thay vì sử dụng vòng lặp.

Ta có thể phân tích tổng như sau: $$\sum_{i=1}^{A} \sum_{j=1}^{B} \sum_{k=1}^{C} ijk = \sum_{i=1}^{A} i \cdot \sum_{j=1}^{B} j \cdot \sum_{k=1}^{C} k$$ Vì $i, j, k$ là các biến独立 (tách biệt), tổng tích bằng tích tổng.

Ta biết công thức tổng các số tự nhiên liên tiếp là: $$\sum_{x=1}^{N} x = \frac{N(N+1)}{2}$$

Như vậy, kết quả cần tìm là: $$\text{Result} = \frac{A(A+1)}{2} \cdot \frac{B(B+1)}{2} \cdot \frac{C(C+1)}{2} = \frac{A(A+1)B(B+1)C(C+1)}{8}$$

Vấn đề cốt lõi là thực hiện tính toán này dưới modulo $998244353$, bao gồm phép chia (nhân với số nghịch đảo modular).

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

Cách Sử dụng số học modulo cơ bản (Nhân với nghịch đảo của 2)

#include <stdio.h>

const long long x = 998244353;

int main(void) {
    int T;
    scanf("%d", &T);

    while (T--) {
        long long A, B, C;
        scanf("%lld%lld%lld", &A, &B, &C);

        // Tính nghịch đảo modular của 2
        // 998244353 là số nguyên tố, (x + 1) / 2 là cách tính nhanh nghịch đảo của 2
        long long inv2 = (x + 1) / 2;

        // Tính S(N) = N*(N+1)/2 % x cho mỗi biến
        A = (A % x) * ((A + 1) % x) % x * inv2 % x;
        B = (B % x) * ((B + 1) % x) % x * inv2 % x;
        C = (C % x) * ((C + 1) % x) % x * inv2 % x;

        // Tích các kết quả lại
        long long tong = A;
        tong = (tong * B) % x;
        tong = (tong * C) % x;

        printf("%lld\n", tong);
    }

    return 0;
}

• Time Complexity: O(T)
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp nhất dựa trên nhận xét toán học. Chúng ta biến đổi tổng thành tích $S(A)S(B)S(C)$ với $S(N) = \frac{N(N+1)}{2}$. Để thực hiện phép chia lấy phần dư, ta cần nhân với số nghịch đảo modular (modular inverse). Vì ta chia cho 2, và $998244353$ là số lẻ, số nghịch đảo của 2 modulo $998244353$ là $(998244353 + 1) / 2 = 499122177$. Code tính $S(N)$ bằng cách nhân $N$, $N+1$, và $inv2$ dưới modulo. Cuối cùng nhân ba kết quả lại. Độ phức tạp là $O(1)$ mỗi test case.

Cách Sử dụng số học modulo với phép chia cho 8

#include <stdio.h>

#define MOD 998244353

long long mod_mul(long long a, long long b) {
    return (a % MOD) * (b % MOD) % MOD;
}

long long mod_pow(long long base, long long exp) {
    long long res = 1;
    while (exp) {
        if (exp % 2 == 1)
            res = mod_mul(res, base);
        base = mod_mul(base, base);
        exp /= 2;
    }
    return res;
}

long long mod_inv(long long x) {
    return mod_pow(x, MOD - 2); // Định lý Fermat nhỏ
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        long long A, B, C;
        scanf("%lld %lld %lld", &A, &B, &C);

        long long partA = mod_mul(A, A + 1);
        long long partB = mod_mul(B, B + 1);
        long long partC = mod_mul(C, C + 1);

        long long result = mod_mul(partA, partB);
        result = mod_mul(result, partC);
        result = mod_mul(result, mod_inv(8)); // chia cho 8 theo modulo

        printf("%lld\n", result);
    }
    return 0;
}

• Time Complexity: O(T \cdot \log MOD)
• Space Complexity: O(1)

Cách này cũng dựa trên công thức $\frac{A(A+1)B(B+1)C(C+1)}{8}$. Nó tính toán tích các phần tử trong tử số trước ($A(A+1)B(B+1)C(C+1)$), sau đó nhân với số nghịch đảo modular của 8. Số nghịch đảo của 8 được tính bằng cách lũy thừa nhanh $8^{MOD-2}$. Cách này đúng nhưng kém hiệu quả hơn so với cách đầu tiên vì tính toán số nghịch đảo cho 8 (hoặc chia làm 3 lần cho 2) tốn kém hơn so với việc tính sẵn $inv2$ và chia ngay trong từng bước tính tổng $S(N)$. Tuy nhiên, về mặt lý thuyết, độ phức tạp vẫn chấp nhận được.

Cách Brute Force (Chỉ dành cho kiểm tra nhỏ)

#include <iostream>
using namespace std;

int main() {
    // Chỉ chạy được với A, B, C nhỏ
    int A = 2, B = 2, C = 2;
    long long sum = 0;
    for (int i = 1; i <= A; i++) {
        for (int j = 1; j <= B; j++) {
            for (int k = 1; k <= C; k++) {
                sum += i * j * k;
            }
        }
    }
    cout << sum << endl;
    return 0;
}

• Time Complexity: O(A * B * C)
• Space Complexity: O(1)

Đây là cách giải quyết trực tiếp bằng cách sử dụng 3 vòng lặp lồng nhau. Nó tính đúng kết quả nhưng độ phức tạp là $O(A \cdot B \cdot C)$, quá lớn so với ràng buộc $A, B, C \le 10^9$. Do đó, phương pháp này không thể sử dụng cho dữ liệu lớn, chỉ dùng để minh họa logic hoặc kiểm tra thủ công với dữ liệu nhỏ.

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

Bài học kinh nghiệm

• Tổng ba vong lặp tich独立 có thể tách thành tích của ba tổng đơn: $\sum{i=1}^{A} \sum{j=1}^{B} \sum{k=1}^{C} ijk = (\sum{i=1}^{A} i)(\sum{j=1}^{B} j)(\sum{k=1}^{C} k)$.
• Công thức tổng các số tự nhiên liên tiếp $1$ đến $N$ là $\frac{N(N+1)}{2}$, giúp giảm độ phức tạp từ $O(N)$ xuống $O(1)$.
• Để thực hiện phép chia trong toán học modular, ta phải nhân với số nghịch đảo modular (modular inverse). Với modulus là số nguyên tố $p$, số nghịch đảo của $a$ là $a^{p-2} \pmod p$.

Lỗi thường gặp

• Tràn số (Integer Overflow): Khi nhân các số lớn như $10^9$ với nhau, kết quả có thể vượt quá giới hạn của kiểu long long (khoảng $9 \times 10^{18}$). Cần phải thực hiện phép nhân modulo ngay lập tức sau mỗi phép nhân.
• Làm tròn sai khi chia: Không được phép chia số nguyên cho số khác rồi lấy phần dư (ví dụ: res / 2 % MOD). Phải dùng số nghịch đảo modular.
• Quên xử lý số nghịch đảo cho 2 hoặc 8: Nếu chỉ tính $A(A+1)B(B+1)C(C+1)$ rồi chia cho 2 hoặc 8 trực tiếp, kết quả sẽ sai.