Hướng dẫn giải của [Beginner Free Contest 11] AVERAGE
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.
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.
Hướng dẫn giải
Đếm số dãy con khác rỗng có trung bình cộng đúng bằng ~a~. Biến đổi ~y_i = x_i - a~ thì bài toán thành đếm tập con khác rỗng có tổng ~y~ bằng 0.
Sub 1: Vét cạn — ~O(2^n \cdot n)~, dùng khi ~n \le 16~
Duyệt mọi tập con bằng bitmask, kiểm tra tổng bằng ~a~ nhân số phần tử. Nếu chỉ nộp sub này: đúng 4/20 test.
Sub 2: Quy hoạch động theo tổng — ~O(n \cdot S)~ với ~S = 80000~
Gọi ~f[s]~ là số tập con (kể cả rỗng) có tổng ~y~ bằng ~s~ (dịch chỉ số để tránh âm). Xét lần lượt từng phần tử, chọn hoặc không chọn. Đáp án là ~f[0] - 1~ (trừ tập rỗng) theo modulo ~10^9+7~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc ~T~ bộ dữ liệu; mỗi bộ có ~n \le 16~ gọi sub1, lớn hơn gọi sub2 (trên 20 test: sub1 xử lý 1 test, sub2 xử lý 19 test). Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
int n, a;
int x[205];
// Sub 1: vét cạn mọi tập con — O(2^n * n), dùng khi n <= 16
long long sub1() {
long long cnt = 0;
for (int mask = 1; mask < (1 << n); mask++) {
long long sum = 0;
int k = 0;
for (int i = 0; i < n; i++)
if (mask >> i & 1) sum += x[i], k++;
if (sum == (long long)a * k) cnt++;
}
return cnt % MOD;
}
// Sub 2: đặt y_i = x_i - a, đếm tập con khác rỗng có tổng y = 0 bằng quy hoạch động theo tổng
long long sub2() {
int OFF = 200 * 200;
vector<int> f(2 * OFF + 1, 0), g;
f[OFF] = 1; // tập rỗng
for (int i = 0; i < n; i++) {
int y = x[i] - a;
g = f;
for (int s = 0; s <= 2 * OFF; s++) {
if (!f[s]) continue;
int t = s + y;
if (t < 0 || t > 2 * OFF) continue;
g[t] += f[s];
if (g[t] >= MOD) g[t] -= MOD;
}
f = g;
}
return (f[OFF] - 1 + MOD) % MOD; // trừ tập rỗng
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int T; cin >> T;
while (T--) {
cin >> n >> a;
for (int i = 0; i < n; i++) cin >> x[i];
if (n <= 16) cout << sub1() << "\n";
else cout << sub2() << "\n";
}
return 0;
}
Bình luận