Hiểu bài toán

Xét một dãy số nguyên $A$ gồm $n$ phần tử $A1, A2, ..., An$. Đếm số lượng cặp chỉ số $(i, j)$ sao cho $1 \le i \le j \le n$ và tổng các phần tử từ $Ai$ đến $A_j$ chia hết cho $d$. Với mỗi test case, nhập vào $d$ và $n$, rồi nhập $n$ số nguyên của dãy. Đầu ra là số lượng cặp thoả mãn.

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

Cách Brute Force (Vét cạn)

int ans = 0;
for (int i = 1; i <= n; i++) {
    long long sum = 0;
    for (int j = i; j <= n; j++) {
        sum += a[j];
        if (sum % d == 0) ans++;
    }
}

• Time Complexity: O(n^2)
• Space Complexity: O(n)

Duyệt qua tất cả các cặp chỉ số $(i, j)$ với $1 \le i \le j \le n$. Với mỗi cặp, tính tổng các phần tử từ $Ai$ đến $Aj$ và kiểm tra xem tổng đó có chia hết cho $d$ hay không. Cách này đơn giản nhưng quá chậm đối với $n$ lớn.

Cách Hash Map (Prefix Sum)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t; cin >> t;
    while(t--) {
        long long d; int n;
        cin >> d >> n;
        vector<long long> a(n+1), prefix(n+1, 0);
        for(int i=1; i<=n; i++) {
            cin >> a[i];
            prefix[i] = prefix[i-1] + a[i];
        }
        unordered_map<long long, int> mp;
        mp[0] = 1;
        long long ans = 0;
        for(int i=1; i<=n; i++) {
            long long r = prefix[i] % d;
            if (r < 0) r += d;
            ans += mp[r];
            mp[r]++;
        }
        cout << ans << "\n";
    }
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Sử dụng mảng cộng dồn (Prefix Sum). Gọi $Pi$ là tổng các phần tử từ $1$ đến $i$. Tổng từ $Ai$ đến $Aj$ là $Pj - P{i-1}$. Điều kiện tổng chia hết cho $d$ tương đương với $Pj \equiv P{i-1} \pmod d$. Ta cần đếm số cặp $(i-1, j)$ có chỉ số cộng dồn chia hết. Sử dụng hash map (unorderedmap) để lưu số lần xuất hiện của các số dư khi chia $Pk$ cho $d$. Với mỗi $Pj$, số cặp thoả mãn là số lần xuất hiện trước đó của $P_j \pmod d$. Phải xử lý số dư âm.

Cách Vector đếm (Frequency Array)

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int d, n;
    cin >> d >> n;
    vector<int> cnt(d, 0);
    cnt[0] = 1;
    int res = 0, cur = 0;
    for(int i=1; i<=n; i++) {
        int x; cin >> x;
        cur = (cur + x) % d;
        cur = (cur + d) % d; // Xử lý âm
        res += cnt[cur];
        cnt[cur]++;
    }
    cout << res << "\n";
}

main() {
    // freopen, ios_base...
    int t; cin >> t;
    while(t--) solve();
}

• Time Complexity: O(n)
• Space Complexity: O(d)

Cách tiếp cận tương tự Hash Map nhưng tối ưu hơn về mặt tốc độ执行. Vì $d$ có giá trị nhỏ (thường thấy trong các bài toán dạng này, ví dụ $d \le 10^5$ hoặc $10^6$), ta có thể dùng một mảng cnt có kích thước $d$ để đếm số lần xuất hiện của các số dư thay vì dùng map. Việc truy cập mảng trực tiếp nhanh hơn truy cập map. Logic tính toán tương tự như cách dùng Hash Map.

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

Bài học kinh nghiệm

• Biến đổi bài toán từ việc tính tổng dãy con sang bài toán về số dư của mảng cộng dồn (Prefix Sum).
• Bài toán quy về đếm số cặp chỉ số $(i, j)$ sao cho $Pi \equiv Pj \pmod d$, trong đó $P_0 = 0$.
• Sử dụng cấu trúc dữ liệu đếm tần suất (Hash Map hoặc Frequency Array) để tối ưu hóa việc tìm kiếm và cập nhật.

Lỗi thường gặp

• Quên xử lý số dư âm khi chia lấy dư ở các ngôn ngữ như C++ (ví dụ: -5 % 3 có thể ra -2 thay vì 1). Cần chuẩn hóa về đoạn $[0, d-1]$ bằng cách (a % d + d) % d.
• Khởi tạo sai giá trị ban đầu cho số dư 0. Vì tổng dãy rỗng (hoặc trước phần tử đầu tiên) là 0, ta phải khởi tạo cnt[0] = 1.