Hiểu bài toán

Cho một dãy số nguyên $A$ gồm $N$ phần tử và một số nguyên dương $K$. Nhiệm vụ của bạn là đếm số lượng dãy con liên tiếp của $A$ sao cho tổng các phần tử trong dãy con đó chia hết cho $K$. Dãy con liên tiếp được định nghĩa là một đoạn con $A[i..j]$ với $1 \le i \le j \le N$.

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

Cách Brute Force

void sub1() {
    int dem = 0;
    FOR(i, 1, n) {
        ll sum = 0;
        FOR(j, i, n) {
            sum += a[j];
            if (sum % k == 0) dem++;
        } 
    }
    cout << dem;
}

• Time Complexity: O(N^2)
• Space Complexity: O(1)

Phương pháp này sử dụng hai vòng lặp lồng nhau để duyệt qua tất cả các dãy con liên tiếp có thể. Vòng lặp ngoài chọn điểm bắt đầu i, vòng lặp trong chọn điểm kết thúc j. Tại mỗi bước, ta cập nhật tổng của dãy con A[i..j] và kiểm tra xem tổng đó có chia hết cho K không. Nếu có thì tăng biến đếm lên 1. Phương pháp này đơn giản để hiểu nhưng chạy chậm, chỉ phù hợp với dữ liệu nhỏ (N <= 2000).

Cách Hash Map (Prefix Sum)

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<ll> a(n + 1);
    vector<ll> pref(n + 1, 0);
    map<ll, int> m;
    m[0] = 1;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i];
    }

    ll cnt = 0;
    for (int i = 1; i <= n; i++) {
        ll mod = (pref[i] % k + k) % k;
        cnt += m[mod];
        m[mod]++;
    }
    cout << cnt;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Đây là phương pháp tối ưu sử dụng kỹ thuật tổng tiền tố (Prefix Sum) và bảng băm (Hash Map).

1. Tổng tiền tố: Gọi $P[i]$ là tổng các phần tử từ $A[1]$ đến $A[i]$. Tổng của dãy con $A[i..j]$ bằng $P[j] - P[i-1]$.
2. Điều kiện chia hết: Dãy con $A[i..j]$ có tổng chia hết cho $K$ khi và chỉ khi $P[j] \equiv P[i-1] (\pmod K)$.
3. Giải pháp: Duyệt qua các vị trí $j$ từ $1$ đến $N$. Với mỗi $P[j]$, ta cần đếm số lượng $i$ ($0 \le i < j$) sao cho $P[i]$ cùng phần dư với $P[j]$ khi chia cho $K$. Ta sử dụng một map (hoặc mảng nếu $K$ nhỏ) để lưu tần suất các phần dư đã gặp.
   • Tại mỗi bước, ta tính phần dư của $P[j]$ modulo $K$.
   • Số lượng dãy con kết thúc tại $j$ có tổng chia hết cho $K$ bằng số lần phần dư này đã xuất hiện trước đó.
   • Sau đó, ta cập nhật tần suất của phần dư này vào map.
   • Ta cần chú ý xử lý phần dư âm cho các ngôn ngữ như C++ (dùng (x % k + k) % k).

Ví dụ: Với $K=3$, nếu các tổng tiền tố là $P[0]=0, P[1]=2, P[2]=5, P[3]=8$. Các phần dư tương ứng là $0, 2, 2, 2$.

• Tại $j=1$: Phần dư 2 (mới gặp 0 lần) -> cộng 0. Thêm 2 vào map.
• Tại $j=2$: Phần dư 2 (đã gặp 1 lần) -> cộng 1. Thêm 2 vào map (tổng 2 lần).
• Tại $j=3$: Phần dư 2 (đã gặp 2 lần) -> cộng 2. Thêm 2 vào map (tổng 3 lần). Tổng cộng: $0+1+2=3$ các dãy con.

Cách Optimized Hash Map (Array)

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

const int MAX = 1e6 + 5;
int cnt[MAX];

int main() {
    int n;
    long long k;
    cin >> n >> k;

    vector<long long> a(n);
    for(int i=0; i<n; i++) cin >> a[i];

    // Xử lý trường hợp K quá lớn (thường là bài toán con chỉ yêu cầu K nhỏ)
    if (k > n + 1) {
        // Logic fallback hoặc xử lý đặc biệt nếu cần
        // Trong bài này thường K nhỏ nên dùng mảng được
    }

    long long sum = 0;
    cnt[0] = 1;
    long long ans = 0;

    for (int i = 0; i < n; i++) {
        sum += a[i];
        long long rem = (sum % k + k) % k;
        ans += cnt[rem];
        cnt[rem]++;
    }
    cout << ans;
}

• Time Complexity: O(N)
• Space Complexity: O(N) or O(K)

Đây là phiên bản tối ưu hóa của phương pháp Hash Map. Thay vì dùng std::map (có độ phức tạp logarit), ta sử dụng một mảng (array) để lưu trữ tần suất phần dư.

• Điều kiện áp dụng: Phương pháp này hiệu quả nhất khi $K$ có giá trị vừa phải (ví dụ $K \le 10^6$), cho phép khai báo mảng có kích thước cố định.
• Cách hoạt động: Logic hoàn toàn tương tự như Hash Map, nhưng việc truy cập và cập nhật mảng cnt[rem] có độ phức tạp hằng số $O(1)$.
• Tối ưu: Thay vì dùng vector hoặc map, việc dùng mảng static giúp giảm thời gian chạy đáng kể, đặc biệt quan trọng trong các kỳ thi lập trình cạnh tranh.

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

Bài học kinh nghiệm

• Bài toán quy về bài toán đếm cặp chỉ số $(i, j)$ sao cho $P[j] \equiv P[i-1] \pmod K$.
• Kỹ thuật Hash Map (hoặc mảng đếm) để lưu tần suất các phần dư của tổng tiền tố là chìa khóa để giảm độ phức tạp từ $O(N^2)$ xuống $O(N)$ hoặc $O(N \log N)$.
• Phần dư âm: Luôn chuẩn hóa phần dư về khoảng $[0, K-1]$ bằng cách (x % K + K) % K để đảm bảo tính chính xác.

Lỗi thường gặp

• Quên xử lý trường hợp phần dư âm trong C++ (ví dụ: -5 % 3 trả về -2 thay vì 1).
• Sử dụng giải thuật $O(N^2)$导致 Timeout cho dữ liệu lớn.
• Sai sót khi khởi tạo mảng đếm: Quên gán cnt[0] = 1 (vì tổng tiền tố tại vị trí 0 là 0, cần đếm cả các dãy con bắt đầu từ đầu mảng).