Hướng dẫn giải của Trung bình cộng


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, Muoikhongman, huut77344, 112611h

Editorial for average: Trung bình cộng

Hiểu bài toán

Cho một dãy số $x1, x2, \dots, xn$. Yêu cầu đếm số lượng dãy con (ngẫu nhiên, không nhất thiết liên tiếp) có trung bình cộng bằng đúng $a$. Đáp án cần được in ra dưới dạng phần dư khi chia cho $10^9 + 7$. Ràng buộc: $n, a \le 200$, $xi \le 200$.

Đề bài có thể được chuyển đổi như sau: Ta cần tìm số lượng dãy con có tổng bằng $a \times k$ với $k$ là số lượng phần tử của dãy con đó. Biến đổi phương trình: $\sum xi = a \cdot k \Rightarrow \sum (xi - a) = 0$. Vì vậy, bài toán quy về việc đếm số lượng dãy con sao cho tổng các phần tử của dãy con sau khi trừ $a$ cho mỗi phần tử bằng 0.

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

Cách Quay lui (Brute Force)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD = 1e9 + 7;

int n, a;
int x[205];
ll ans = 0;

void backtrack(int i, int current_sum, int count) {
    if (i == n + 1) {
        if (count > 0 && current_sum == 0) {
            ans = (ans + 1) % MOD;
        }
        return;
    }
    // Chọn phần tử thứ i
    backtrack(i + 1, current_sum + x[i] - a, count + 1);
    // Không chọn phần tử thứ i
    backtrack(i + 1, current_sum, count);
}

void solve() {
    cin >> n >> a;
    for (int i = 1; i <= n; i++) cin >> x[i];
    ans = 0;
    backtrack(1, 0, 0);
    cout << ans << endl;
}

int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}
  • Time Complexity: O(2^n)
  • Space Complexity: O(n)

Đây là cách giải trực tiếp nhất. Duyệt qua tất cả các dãy con có thể có (bao gồm cả dãy rỗng). Với mỗi dãy con, tính tổng các phần tử sau khi trừ $a$ và kiểm tra xem tổng có bằng 0 hay không. Nếu có và dãy con không rỗng thì tăng biến đếm. Do $n$ tối đa lên tới 200, độ phức tạp $2^{200}$ là quá lớn nên phương pháp này chỉ khả thi cho các test rất nhỏ (Subtask 1).

Cách Quy hoạch động dựa trên tổng (Sum DP)
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 200;
const int MAXA = 200;
const int SHIFT = MAXN * MAXA; // Khoảng giá trị tổng có thể là [-40000, 40000]

int dp[MAXN + 1][2 * SHIFT + 1];

void solve() {
    int n, a;
    cin >> n >> a;
    vector<int> x(n);
    for (int i = 0; i < n; i++) cin >> x[i];

    // Khởi tạo bảng DP
    for (int i = 0; i <= n; i++) {
        fill(dp[i], dp[i] + 2 * SHIFT + 1, 0);
    }
    dp[0][SHIFT] = 1;

    for (int i = 1; i <= n; i++) {
        int diff = x[i - 1] - a;
        for (int j = 0; j <= 2 * SHIFT; j++) {
            // Cách 1: Không chọn x[i-1]
            dp[i][j] = dp[i - 1][j];
            // Cách 2: Có chọn x[i-1]
            if (j - diff >= 0 && j - diff <= 2 * SHIFT) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j - diff]) % MOD;
            }
        }
    }

    // Đáp án là số cách chọn (bất kỳ subset nào) có tổng bằng 0, trừ đi 1 (trường hợp subset rỗng)
    cout << (dp[n][SHIFT] - 1 + MOD) % MOD << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}
  • Time Complexity: O(n \cdot S) với S là khoảng giá trị tổng (khoảng 80000)
  • Space Complexity: O(n \cdot S)

Bài toán yêu cầu đếm các dãy con sao cho tổng các phần tử trừ đi $a$ bằng 0. Xét $diffi = xi - a$. Ta cần đếm số cách chọn các phần tử sao cho tổng $\sum diffi = 0$. Sử dụng quy hoạch động 2 chiều: $dp[i][s]$ là số cách chọn các phần tử từ $i$ phần tử đầu tiên để được tổng là $s$.Do $xi \le 200, a \le 200$ và $n \le 200$, tổng giá trị $diff$ nằm trong khoảng $[-40000, 40000]$. Ta cần một offset (SHIFT) để lưu các tổng âm vào mảng. Công thức chuyển trạng thái: $dp[i][s] = dp[i-1][s] + dp[i-1][s - diff_i]$. Đáp án là $dp[n][0]$ (tại vị trí SHIFT) trừ đi 1 (trường hợp không chọn phần tử nào).

Cách Quy hoạch động tối ưu bộ nhớ (1D Sum DP)
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 200;
const int MAXA = 200;
const int SHIFT = 200 * 200;
const int MAX_SUM = 2 * SHIFT + 1;

int dp[MAX_SUM];

void solve() {
    int n, a;
    cin >> n >> a;
    vector<int> x(n);
    for (int i = 0; i < n; i++) cin >> x[i];

    // Reset DP array
    memset(dp, 0, sizeof(dp));
    dp[SHIFT] = 1; // Khởi tạo tổng 0 (subset rỗng)

    for (int i = 0; i < n; i++) {
        int diff = x[i] - a;
        // Duyệt ngược để tránh dùng lại phần tử đang xét (knapsack style)
        // Hoặc duyệt xuôi với mảng phụ, nhưng với bài toán subset sum thì duyệt ngược thường dùng mảng 1D
        // Tuy nhiên, công thức $dp[s] = dp[s] + dp[s - diff]$ nếu duyệt xuôi sẽ tính đúng vì ta đang xét thêm 1 phần tử mới
        // Nhưng cẩn thận với việc tính toán:
        // Nếu dùng mảng 1D và cập nhật tại chỗ, ta phải duyệt tổng từ cao xuống thấp nếu diff > 0 (để tránh dùng lại phần tử mới).
        // Ở đây bài toán là đếm subset, không phải số cách (với số lượng phần tử không giới hạn).
        // Với đếm subset, ta dùng mảng 2 chiều hoặc mảng 1 chiều với thứ tự duyệt hợp lý.
        // Đơn giản nhất là dùng mảng 2 chiều, hoặc mảng 1 chiều nhưng duyệt tổng hợp lý.
        // 
        // Cách tiếp cận mảng 1 chiều chuẩn cho subset sum:
        // Duyệt tổng s từ MAX_SUM-1 về 0:
        //   dp[s] = (dp[s] + dp[s - diff]) % MOD;
        // (Cần kiểm tra điều kiện biên)

        vector<int> new_dp(dp, dp + MAX_SUM);
        for (int s = 0; s < MAX_SUM; s++) {
            if (dp[s] != 0) {
                int next_s = s + diff;
                if (next_s >= 0 && next_s < MAX_SUM) {
                    new_dp[next_s] = (new_dp[next_s] + dp[s]) % MOD;
                }
            }
        }
        memcpy(dp, new_dp.data(), sizeof(dp));
    }

    cout << (dp[SHIFT] - 1 + MOD) % MOD << endl;
}

int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}
  • Time Complexity: O(n \cdot S)
  • Space Complexity: O(S)

Đây là phiên bản tối ưu bộ nhớ của phương pháp DP dựa trên tổng. Thay vì lưu bảng 2 chiều $dp[i][s]$, ta chỉ cần lưu $dp[s]$ là số cách tạo ra tổng $s$. Ban đầu, $dp[0] = 1$ (dùng offset). Với mỗi phần tử $xi$, ta cập nhật mảng $dp$. Nếu ta thêm $xi$ vào các dãy con hiện tại có tổng $s$, ta được các dãy con có tổng $s + diff$. Do ta không được dùng lại phần tử $x_i$ nhiều lần (chỉ chọn hoặc không chọn), ta cần duyệt sao cho mỗi phần tử chỉ được xử lý 1 lần. Dùng mảng phụ new_dp hoặc duyệt ngược s để đảm bảo tính đúng. Ví dụ: new_dp[s + diff] += dp[s]. Cuối cùng, đáp án là dp[SHIFT] - 1.

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

Cách tiếp cận Time Space Tên
1 O(2^n) O(n) Quay lui (Brute Force)
2 O(n \cdot S) với S là khoảng giá trị tổng (khoảng 80000) O(n \cdot S) Quy hoạch động dựa trên tổng (Sum DP)
3 O(n \cdot S) O(S) Quy hoạch động tối ưu bộ nhớ (1D Sum DP)

Bài học kinh nghiệm

  • Bài toán trung bình cộng có thể biến đổi thành bài toán tổng: $\sum xi = a \cdot k \iff \sum (xi - a) = 0$.
  • Vì các giá trị $x_i$ và $a$ nhỏ, tổng chênh lệch nằm trong một khoảng nhỏ, cho phép sử dụng mảng quy hoạch động trực tiếp thay vì map.
  • Bài toán đếm số lượng dãy con tương đương bài toán 'Subset Sum' (đếm số lượng tập con có tổng bằng 0).

Lỗi thường gặp

  • Quên trừ đi 1 để loại trừ trường hợp dãy con rỗng (vì đề bài yêu cầu dãy con có ít nhất một phần tử).
  • Sử dụng sai hướng duyệt trong quy hoạch động 1D dẫn đến việc tính toán sai (dùng lại phần tử nhiều lần hoặc không tính đúng các trường hợp kết hợp).
  • Quên sử dụng Offset (SHIFT) khi lưu các tổng âm vào mảng.

Bình luận

Please read the guidelines before commenting.


Không có bình luận tại thời điểm này.