Hướng dẫn cho LQDOJ Cup 2023 - Round 5 - Slime
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Subtask \(1\)
Tutorial
Duyệt từng cách cách mua rồi kiểm tra xem có thoả mãn điều kiện hay không rồi cập nhật đáp án.
Có nhiều cách để kiểm tra, một trong số cách đó là sử dụng hàng đợi ưu tiên.
Độ phức tạp: \(O(2^n \times n \log n)\).
Subtask \(2\)
Tutorial
Tách \(s = d \times 2^k\) sao cho \(k\) lớn nhất có thể. Nhận xét là chỉ những con slime có kích thước dạng \(d \times 2^t\) (\(0 \leq t \leq k\)) mới có khả năng gộp với những con slime khác để tạo thành con slime có kích thước \(s\).
Xét một cách mua, ta luôn gộp những con slime có kích thước bằng nhau cho đến khi không thể gộp nữa. Với \(s \leq 5 \times 10^3\) thì \(k \leq 12\), nghĩa là chỉ có tối đa \(13\) kích thước phân biệt (\(0, 1, 2, \ldots, 12\)) nên ta có thể lưu một cách mua thành một dãy bit (bit thứ \(i\) là \(1\) nghĩa là tồn tại con slime có kích thước \(d \times 2^i\) trong cách mua và \(0\) là ngược lại).
Gọi \(dp(i, mask)\) là số cách mua thoả mãn xét đến con slime thứ \(i\) và cách mua hiện tại được lưu thành một dãy bit tên là \(mask\).
Có hai trường hợp:
- Không chọn con slime thứ \(i\): \(dp(i + 1, mask)\)
- Chọn con slime thứ \(i\):
- Không gộp được: \(dp(i + 1, mask)\)
- Gộp được: \(dp(i + 1, mask + 2^t)\) với \(a_i = d \times 2^t\)
Khi bit thứ \(k\) của \(mask\) được bật nghĩa là cách mua hiện tại đã thoả mãn, ta phải xử lý khéo để bit này vẫn luôn bật (tránh trường hợp tạo ra số lớn hơn và làm tắt bit).
Độ phức tạp: \(O(n \times s)\).
Subtask \(3\)
Tutorial
Vẫn tách \(s = d \times 2^k\), \(a = d \times 2^t\) (nếu không tách \(a\) được thì đáp án là \(0\)).
Một cách mua thoả mãn cần ít nhất \(2^{k - t}\) con slime nên đáp án là
Để tính \(\binom{n}{k}\), ta có thể sử dụng nghịch đảo modulo.
Độ phức tạp: \(O(n)\).
Subtask \(4\)
Tutorial
Tiếp tục ý tưởng subtask 2, gọi \(cnt_i\) là số lượng con slime có kích thước \(d \times 2^i\). Những số không được tính sẽ được đếm lại là \(rem\) và nhân vào kết quả cuối cùng một lượng \(2^{rem}\).
Gọi \(dp(i, mask)\) là số cách mua thoả mãn xét đến các con slime có kích thước \(d \times 2^i\) và cách mua hiện tại được lưu thành một dãy bit tên là \(mask\).
Xét đến \(i\), ta sẽ chọn một lượng các con slime để thêm vào cách mua hiện tại. Giả sử số lượng ta chọn là \(x\) (\(0 \leq x \leq cnt_i\)), số lượng cách mua thoả mãn là \(\binom{cnt_i}{x} \times dp(i + 1, mask + x \times 2^i)\).
Nhận xét là tại 𝑖, số lượng con slime kích thước \(d \times 2^i\) cần dùng để tạo thành con slime có kích thước \(d \times 2^k\) không vượt quá \(2^{k - i}\). Vậy nên thay vì duyệt từ \(0\) đến \(cnt_i\), ta duyệt đến \(\min(cnt_i, 2^{k - i})\) hoặc đến khi bit thứ \(k\) của \(mask\) được bật.
Độ phức tạp: \(O(n + s^2)\).
Chứng minh độ phức tạp: Tại mỗi \(i\), ta duyệt tối đa \(2^{k - i}\) lần nên tổng độ phức tạp là
Solution
#include <bits/stdc++.h>
/// kitsune
using namespace std;
#define fi first
#define se second
#define mp make_pair
//#define int long long
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = (int)(l); i <= (int)(r); i++)
#define per(i, r, l) for (int i = (int)(r); i >= (int)(l); i--)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename _Tp> bool minimize(_Tp& __a, const _Tp& __b) { if (__a > __b) { __a = __b; return true; } return false; }
template<typename _Tp> bool maximize(_Tp& __a, const _Tp& __b) { if (__a < __b) { __a = __b; return true; } return false; }
const int siz = 2e5 + 2;
const int SIZ = 5e3 + 2;
const int mod = 1e9 + 7;
const int maxx = 2e9;
const ll MAXX = 1e18;
const string file = "slime";
int quick_pow(int x, int n) {
int res = 1;
for ( ; n; n /= 2, x = x * (ll)x % mod) {
if (n % 2 == 1) {
res = res * (ll)x % mod;
}
}
return res;
}
int fact[siz], inv_fact[siz];
int choose(int n, int k) {
if (n < 0 || k < 0 || n < k) {
return 0;
}
return fact[n] * (ll)inv_fact[k] % mod * inv_fact[n - k] % mod;
}
int m;
int a[siz];
int cnt[13];
int f[13][1 << 13]; bool g[13][1 << 13];
int dp(int pos, int mask) {
if (pos == m + 1) {
return (mask >> m) & 1;
}
int &res = f[pos][mask];
bool &cal = g[pos][mask];
if (cal) {
return res;
}
int new_mask = (mask & (1 << m)) ? (1 << m) : mask;
int rem_choose = quick_pow(2, cnt[pos]);
res = 0;
rep (i, 0, cnt[pos]) {
(res += choose(cnt[pos], i) * (ll)dp(pos + 1, new_mask) % mod) %= mod;
if (new_mask & (1 << m)) {
new_mask = 1 << m;
} else {
new_mask += 1 << pos;
}
(rem_choose -= choose(cnt[pos], i) - mod) %= mod;
if (new_mask & (1 << m)) {
break;
}
}
(res += rem_choose * (ll)dp(pos + 1, 1 << m) % mod) %= mod;
cal = true;
return res;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen((file + ".inp").c_str(), "r")) {
freopen((file + ".inp").c_str(), "r", stdin);
freopen((file + ".out").c_str(), "w", stdout);
}
fact[0] = 1;
rep (i, 1, siz - 1) {
fact[i] = fact[i - 1] * (ll)i % mod;
}
inv_fact[siz - 1] = quick_pow(fact[siz - 1], mod - 2);
per (i, siz - 2, 0) {
inv_fact[i] = inv_fact[i + 1] * (ll)(i + 1) % mod;
}
int n, s;
cin >> n >> s;
rep (i, 1, n) {
cin >> a[i];
}
m = 0;
while (s % 2 == 0) {
m++;
s /= 2;
}
int out = 0;
rep (i, 1, n) {
if (a[i] % s != 0) {
out++;
continue;
}
if (__builtin_popcount(a[i] / s) == 1) {
cnt[__builtin_ctz(a[i] / s)]++;
} else {
out++;
}
}
cout << dp(0, 0) * (ll)quick_pow(2, out) % mod << "\n";
// cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}
Bình luận