Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Do not try to preserve the chosen subset's original order. Once a subset is chosen, sorting is forced, so while scanning strengths from large to small the key variable is just: how many reindeer have already been chosen?
For the -th chosen reindeer after sorting, with exponent , the contribution is if , otherwise . Since the sorted exponents are non-increasing, the values are strictly decreasing. So the capacity has no binary carries. That's the crack in the wall.
Think of the capacity as a binary mask. If bit is set and there are already larger set bits, then the reindeer creating this bit must have exponent .
Consecutive set bits in the capacity correspond to reindeer with the same exponent. A run of length therefore contributes a factor .
Run digit DP over bits from down to . Track whether the capacity prefix is equal to or greater than , how many set bits have been placed, and the current run length of consecutive ones. After the mask is fixed, multiply by the ways to add zero-contributing reindeer.
The first trap is thinking the floors create messy carries. They don't. Powers of two are doing a lot of unpaid labor here.
Take a chosen subset and sort its exponents in non-increasing order:
The -th chosen reindeer contributes
Now compare two consecutive positive contribution exponents:
So the positive exponents are strictly decreasing. That means the carrying capacity is exactly a binary mask: every contributing reindeer sets one distinct bit, and there are no carries. Huge simplification.
Mapping capacity bits back to reindeer
Suppose we build the capacity mask from high bit to low bit.
If we set bit , and we have already set larger bits, then this bit is produced by the -th contributing reindeer. Its exponent must be
So setting bit means choosing one more reindeer from bucket .
If two set bits are consecutive, say and then , they map to the same exponent:
Therefore a run of consecutive set bits maps to choosing reindeer from one exponent bucket, giving factor
That's why the DP tracks the current run length.
Digit DP
We process bits from down to . Bit is enough because all original exponents are at most , and every positive contribution exponent is at most .
Let
mean:
At bit , we try placing or .
Placing is allowed unless we are equal so far and has bit here, because that would make the capacity smaller forever. Lower bits cannot repair that. Binary is merciless.
Placing uses exponent
If the current run length is , extending the run changes the bucket factor from
to
The multiplier is therefore
We do this modulo using modular inverses.
Zero-contributing reindeer
After the capacity mask is fixed, suppose it has set bits. These are the contributing reindeer.
Any extra selected reindeer must contribute zero. The next selected position would be divided by , so any extra reindeer with exponent at most contributes zero. Since the order is sorted, all later ones also contribute zero.
So:
Which is that? Exactly the number of trailing ones at the bottom of the capacity mask. That is precisely the final run length in the DP.
Thus the final multiplier is
but remember: the DP already included an exact factor when . So in code we replace that exact factor by the suffix sum using
For , there was no exact factor yet, so the suffix sum is just multiplied directly.
Complexity
The DP has about
states/transitions per query. Updates only change one count bucket. This is tiny for .
The big false assumption to avoid: you do not need to store capacities up to . can be , and allocating that array is how you turn your laptop into a very expensive sadness generator.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int addmod(int a, int b) {
a += b;
if (a >= MOD) a -= MOD;
return a;
}
int modpow(long long a, long long e) {
long long r = 1;
while (e) {
if (e & 1) r = r * a % MOD;
a = a * a % MOD;
e >>= 1;
}
return (int)r;
}
int main() {
setIO();
int n, m;
cin >> n >> m;
int maxN = n + m + 5;
vector<int> fact(maxN + 1), ifact(maxN + 1), inv(maxN + 2), pow2(maxN + 1);
fact[0] = 1;
for (int i = 1; i <= maxN; i++) fact[i] = 1LL * fact[i - 1] * i % MOD;
ifact[maxN] = modpow(fact[maxN], MOD - 2);
for (int i = maxN; i >= 1; i--) ifact[i - 1] = 1LL * ifact[i] * i % MOD;
inv[1] = 1;
for (int i = 2; i <= maxN + 1; i++) {
inv[i] = MOD - 1LL * (MOD / i) * inv[MOD % i] % MOD;
}
pow2[0] = 1;
for (int i = 1; i <= maxN; i++) pow2[i] = addmod(pow2[i - 1], pow2[i - 1]);
auto C = [&](int nn, int rr) -> int {
if (rr < 0 || rr > nn) return 0;
return 1LL * fact[nn] * ifact[rr] % MOD * ifact[nn - rr] % MOD;
};
auto invC = [&](int nn, int rr) -> int {
return 1LL * ifact[nn] * fact[rr] % MOD * fact[nn - rr] % MOD;
};
vector<vector<int>> suf(maxN + 1, vector<int>(maxN + 2));
for (int i = 0; i <= maxN; i++) {
for (int j = i; j >= 0; j--) {
suf[i][j] = addmod(suf[i][j + 1], C(i, j));
}
}
vector<int> cnt(61);
for (int i = 0; i < n; i++) {
int c;
cin >> c;
cnt[c]++;
}
auto solve = [&](unsigned long long x) -> int {
vector<int> pref(62, 0);
for (int i = 0; i < 61; i++) pref[i + 1] = pref[i] + cnt[i];
static int dp[2][62][62], ndp[2][62][62];
memset(dp, 0, sizeof(dp));
dp[0][0][0] = 1;
for (int b = 60; b >= 0; b--) {
memset(ndp, 0, sizeof(ndp));
int xb = (x >> b) & 1ULL;
for (int cmp = 0; cmp < 2; cmp++) {
for (int p = 0; p <= 61; p++) {
for (int r = 0; r <= 61; r++) {
int ways = dp[cmp][p][r];
if (!ways) continue;
if (cmp || xb == 0) {
ndp[cmp][p][0] = addmod(ndp[cmp][p][0], ways);
}
int ncmp = cmp;
if (!cmp && xb == 0) ncmp = 1;
int e = b + p;
if (e <= 60 && p + 1 <= 61 && r + 1 <= 61 && r + 1 <= cnt[e]) {
int mult = 1LL * (cnt[e] - r) * inv[r + 1] % MOD;
int &cell = ndp[ncmp][p + 1][r + 1];
cell = (cell + 1LL * ways * mult) % MOD;
}
}
}
}
memcpy(dp, ndp, sizeof(dp));
}
int ans = 0;
for (int cmp = 0; cmp < 2; cmp++) {
for (int l = 1; l <= 61; l++) {
for (int r = 0; r <= l; r++) {
int ways = dp[cmp][l][r];
if (!ways || r > cnt[l - 1]) continue;
int extra = pow2[pref[l - 1]];
int boundary = suf[cnt[l - 1]][r];
if (r > 0) boundary = 1LL * boundary * invC(cnt[l - 1], r) % MOD;
int add = 1LL * ways * extra % MOD * boundary % MOD;
ans = addmod(ans, add);
}
}
}
return ans;
};
while (m--) {
int type;
unsigned long long x;
cin >> type >> x;
if (type == 1) {
cnt[(int)x]++;
} else if (type == 2) {
cnt[(int)x]--;
} else {
cout << solve(x) << '\n';
}
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int addmod(int a, int b) {
a += b;
if (a >= MOD) a -= MOD;
return a;
}
int modpow(long long a, long long e) {
long long r = 1;
while (e) {
if (e & 1) r = r * a % MOD;
a = a * a % MOD;
e >>= 1;
}
return (int)r;
}
int main() {
setIO();
int n, m;
cin >> n >> m;
int maxN = n + m + 5;
vector<int> fact(maxN + 1), ifact(maxN + 1), inv(maxN + 2), pow2(maxN + 1);
fact[0] = 1;
for (int i = 1; i <= maxN; i++) fact[i] = 1LL * fact[i - 1] * i % MOD;
ifact[maxN] = modpow(fact[maxN], MOD - 2);
for (int i = maxN; i >= 1; i--) ifact[i - 1] = 1LL * ifact[i] * i % MOD;
inv[1] = 1;
for (int i = 2; i <= maxN + 1; i++) {
inv[i] = MOD - 1LL * (MOD / i) * inv[MOD % i] % MOD;
}
pow2[0] = 1;
for (int i = 1; i <= maxN; i++) pow2[i] = addmod(pow2[i - 1], pow2[i - 1]);
auto C = [&](int nn, int rr) -> int {
if (rr < 0 || rr > nn) return 0;
return 1LL * fact[nn] * ifact[rr] % MOD * ifact[nn - rr] % MOD;
};
auto invC = [&](int nn, int rr) -> int {
return 1LL * ifact[nn] * fact[rr] % MOD * fact[nn - rr] % MOD;
};
vector<vector<int>> suf(maxN + 1, vector<int>(maxN + 2));
for (int i = 0; i <= maxN; i++) {
for (int j = i; j >= 0; j--) {
suf[i][j] = addmod(suf[i][j + 1], C(i, j));
}
}
vector<int> cnt(61);
for (int i = 0; i < n; i++) {
int c;
cin >> c;
cnt[c]++;
}
auto solve = [&](unsigned long long x) -> int {
vector<int> pref(62, 0);
for (int i = 0; i < 61; i++) pref[i + 1] = pref[i] + cnt[i];
static int dp[2][62][62], ndp[2][62][62];
memset(dp, 0, sizeof(dp));
dp[0][0][0] = 1;
for (int b = 60; b >= 0; b--) {
memset(ndp, 0, sizeof(ndp));
int xb = (x >> b) & 1ULL;
for (int cmp = 0; cmp < 2; cmp++) {
for (int p = 0; p <= 61; p++) {
for (int r = 0; r <= 61; r++) {
int ways = dp[cmp][p][r];
if (!ways) continue;
if (cmp || xb == 0) {
ndp[cmp][p][0] = addmod(ndp[cmp][p][0], ways);
}
int ncmp = cmp;
if (!cmp && xb == 0) ncmp = 1;
int e = b + p;
if (e <= 60 && p + 1 <= 61 && r + 1 <= 61 && r + 1 <= cnt[e]) {
int mult = 1LL * (cnt[e] - r) * inv[r + 1] % MOD;
int &cell = ndp[ncmp][p + 1][r + 1];
cell = (cell + 1LL * ways * mult) % MOD;
}
}
}
}
memcpy(dp, ndp, sizeof(dp));
}
int ans = 0;
for (int cmp = 0; cmp < 2; cmp++) {
for (int l = 1; l <= 61; l++) {
for (int r = 0; r <= l; r++) {
int ways = dp[cmp][l][r];
if (!ways || r > cnt[l - 1]) continue;
int extra = pow2[pref[l - 1]];
int boundary = suf[cnt[l - 1]][r];
if (r > 0) boundary = 1LL * boundary * invC(cnt[l - 1], r) % MOD;
int add = 1LL * ways * extra % MOD * boundary % MOD;
ans = addmod(ans, add);
}
}
}
return ans;
};
while (m--) {
int type;
unsigned long long x;
cin >> type >> x;
if (type == 1) {
cnt[(int)x]++;
} else if (type == 2) {
cnt[(int)x]--;
} else {
cout << solve(x) << '\n';
}
}
return 0;
}