Hiểu bài toán

Cho một dãy số $A$ gồm $n$ phần tử và các số nguyên dương $k, S$. Nhiệm vụ là đếm số lượng đoạn con liên tiếp của dãy sao cho:

1. Độ dài của đoạn con chia hết cho $k$.
2. Tổng các phần tử trong đoạn con đó lớn hơn hoặc bằng $S$.

Đề bài yêu cầu xử lý với $n$ lên tới $10^6$, do đó cần một giải pháp hiệu quả về mặt thời gian.

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

Cách Duyệt tất cả các đoạn con (Brute Force)

for (int l = 1; l <= n; l++) {
    for (int len = k; len <= n - l + 1; len += k) {
        if (sum(l, l + len - 1) >= S) ans++;
    }
}

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

Phương pháp này duyệt qua tất cả các đoạn con thỏa mãn điều kiện độ dài chia hết cho $k$. Với mỗi điểm đầu $l$, ta thử các độ dài $k, 2k, 3k, ...$. Với mỗi đoạn, ta kiểm tra tổng của nó (có thể dùng mảng cộng dồn để tính nhanh). Phương pháp này quá chậm và chỉ có thể chạy đúng với $n$ nhỏ (ví dụ $n \le 10^4$).

Cách Chia theo số dư khi chia cho k (Two Pointers / Sliding Window)

// Pseudocode
for (int r = 0; r < k; r++) {
    vector<long long> B;
    for (int i = r; i <= n; i += k) B.push_back(pref[i]);
    // Duyệt hai con trỏ hoặc dùng cấu trúc dữ liệu để đếm
    // Tìm các cặp (i, j) sao cho B[j] - B[i] >= S
}

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

Giả sử ta xét đoạn con từ chỉ số $l$ đến $r$. Điều kiện độ dài chia hết cho $k$ tương đương với $(r - l + 1) \equiv 0 \pmod k$, hay $l \equiv r + 1 \pmod k$. Do đó, ta có thể chia các chỉ số của mảng cộng dồn thành $k$ nhóm dựa trên số dư của chỉ số khi chia cho $k$. Với mỗi nhóm, ta chỉ cần xét các cặp chỉ số $(i, j)$ thỏa mãn $i < j$ và $P[j] - P[i] \ge S$. Bài toán quy về đếm số cặp $(i, j)$ trong mỗi nhóm thỏa mãn điều kiện tổng. Có thể dùng hai con trỏ (nếu sắp xếp) hoặc cấu trúc dữ liệu như Fenwick Tree / Segment Tree.

Cách Giải pháp tối ưu với Hai con trỏ (Two Pointers)

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

int main() {
    int n; long long k, S;
    cin >> n >> k >> S;
    vector<long long> pref(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        long long a; cin >> a;
        pref[i] = pref[i-1] + a;
    }

    long long ans = 0;
    // Xét từng nhóm theo số dư r
    for (int r = 0; r < k; ++r) {
        vector<long long> B;
        // Lấy các giá trị prefix sum tại các chỉ số i sao cho (i+1) % k == r
        // Chú ý: Đoạn con từ l đến r có tổng là pref[r] - pref[l-1]
        // Độ dài r - (l-1) chia hết cho k => (r) % k == (l-1) % k
        // Ta cần chia các chỉ số i (của pref) thành nhóm theo i % k
        for (int i = r; i <= n; i += k) {
            B.push_back(pref[i]);
        }

        int m = B.size();
        int j = 0;
        for (int i = 0; i < m; ++i) {
            if (j < i + 1) j = i + 1;
            while (j < m && B[j] - B[i] < S) {
                j++;
            }
            if (j < m) {
                ans += (m - j);
            }
        }
    }
    cout << ans;
    return 0;
}

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

Đây là cách tiếp cận hiệu quả nhất.

1. Xây dựng mảng cộng dồn $P$, trong đó $P[x]$ là tổng từ $A[1]$ đến $A[x]$.
2. Tổng của đoạn con từ $l$ đến $r$ là $P[r] - P[l-1]$. Điều kiện độ dài chia hết cho $k$ ($r - l + 1$ chia hết cho $k$) tương đương với $r \equiv l-1 \pmod k$.
3. Do đó, ta chỉ cần xét các cặp chỉ số $(l-1, r)$ trong mảng $P$ mà có cùng số dư khi chia cho $k$.
4. Với mỗi số dư $r \in {0, ..., k-1}$, ta tạo một danh sách các giá trị $P[i]$ tại các chỉ số $i$ có $i \equiv r \pmod k$. Danh sách này được sắp xếp theo thứ tự xuất hiện tự nhiên (tăng dần chỉ số).
5. Với mỗi danh sách, ta dùng kỹ thuật hai con trỏ (hoặc duyệt tuần tự) để đếm số cặp $(i, j)$ ($i < j$) sao cho $P[j] - P[i] \ge S$. Vì chỉ số $j$ tăng dần, ta có thể tối ưu để chỉ duyệt qua danh sách một lần.
6. Độ phức tạp là $O(n)$ vì mỗi phần tử chỉ được xử lý một vài lần.

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

Bài học kinh nghiệm

• Biến đổi điều kiện độ dài chia hết cho $k$ thành điều kiện về số dư của chỉ số trong mảng cộng dồn: $r \equiv l-1 \pmod k$.
• Sử dụng mảng cộng dồn để tính tổng đoạn con trong thời gian $O(1)$.
• Phương pháp tối ưu chia nhỏ bài toán thành $k$ bài toán con độc lập, mỗi bài toán con có thể giải quyết bằng thuật toán hai con trỏ với độ phức tạp tuyến tính.

Lỗi thường gặp

• Lỗi Index Out of Bounds: Khi sử dụng mảng, cần chú ý các chỉ số bắt đầu từ 0 hay 1 và kích thước mảng cộng dồn là $n+1$ (bao gồm cả $P[0] = 0$).
• Lỗi logic về số dư: Cần xác định đúng công thức quy đổi từ $(l, r)$ sang các chỉ số trong mảng cộng dồn để phân nhóm chính xác.
• Không tối ưu được thuật toán hai con trỏ: Nếu duyệt cẩn thận, có thể đảm bảo độ phức tạp $O(n)$. Nếu không, có thể bị trượt vào độ phức tạp $O(n \log n)$ hoặc tệ hơn.