Christmas Reindeer (hard version)

The Bitmask Hiding In Plain Sight

Suppose we choose some reindeer and sort their exponents in non-increasing order:

$b_1\ge b_2\ge \dots \ge b_k.$

The actual strengths are $2^{b_i}$, so the $j$-th selected reindeer contributes

$\left\lfloor \frac{2^{b_j}}{2^{j-1}} \right\rfloor.$

That is either

$2^{b_j-j+1}$

if $b_j\ge j-1$, or $0$ otherwise.

Now the important part:

$b_{j+1}-j \le b_j-j = (b_j-j+1)-1.$

So the positive contribution exponents

$b_j-j+1$

are strictly decreasing. Therefore the carrying capacity has no repeated powers of two and no carries. It is just a binary mask. Very cute. Also very easy to miss, because the statement is doing its best to look like a tax form.

Exact Capacity Shape

Say a positive capacity has set bits

$d_1>d_2>\dots>d_t\ge 0.$

If these are the positive contributions, then the $j$-th positive-contributing reindeer must have exponent

$e_j=d_j+j-1.$

So the required exponents are forced.

After these $t$ positive contributors, any extra selected reindeer must contribute $0$. The next selected reindeer would be in position $t+1$, so it contributes positively iff its exponent is at least $t$. Therefore zero-tail reindeer can only have exponent $<t$.

This gives an exact counting formula, but summing it over all capacities is impossible directly. There are way too many masks. We need to count all capacities below $x$ by binary prefix logic.

Counting Capacities Less Than $x$

We compute the number of selected subsets whose carrying capacity is $<x$, then subtract from all subsets.

Scan bits from $60$ down to $0$. Bit $60$ is enough because strengths are at most $2^{60}$, so the highest possible contribution bit is $60$.

Maintain:

• $h$: how many higher bits of the capacity have already been fixed to $1$ while matching the prefix of $x$;
• ways: the number of ways to choose the forced reindeer for that equal prefix;
• used[e]: how many forced reindeer of exponent $e$ the current prefix already needs.

Now suppose we are at bit $p$ and the higher bits are still equal to $x$.

If $x_p=1$, then capacities smaller than $x$ can be formed by setting this capacity bit to $0$ and making all lower bits arbitrary.

Since $h$ higher positive bits were already chosen, a reindeer that would create bit $p$ must have exponent

$e=p+h.$

If we set bit $p$ to $0$, then all future positive contributions must use exponents at most $e-1$. And once we are already smaller than $x$, lower bits do not matter anymore. So every remaining reindeer with exponent $\le e-1$ may be chosen or not chosen freely.

That contributes

$ways\cdot 2^{pref[e-1]},$

where $pref[q]$ is the number of current reindeer with exponent at most $q$.

Then, to keep matching $x$, since $x_p=1$, we must force bit $p$ to be $1$. That means choosing one more reindeer of exponent $e=p+h$.

If we already used $r$ reindeer of this exponent in the forced prefix, the binomial factor changes from

$\binom{cnt[e]}{r}$

to

$\binom{cnt[e]}{r+1}.$

So multiply by

$\frac{cnt[e]-r}{r+1}.$

Modulo $998244353$, division means multiplying by modular inverse. Since $r\le 61$, we can precompute these tiny inverses. If $e>60$ or $cnt[e]=r$, the prefix becomes impossible and ways becomes $0$.

If $x_p=0$, we do not add anything; we simply keep matching the prefix with bit $0$.

At the end, the accumulated value is exactly the number of subsets with carrying capacity $<x$.

Why The Free Lower Choices Work

This is the part worth double-checking, because otherwise the solution feels like black magic.

When the prefix has $h$ already selected positive contributors and we skip bit $p$, exponent $p+h$ is forbidden. Any later positive contributor is placed after those $h$ contributors, so to create a lower bit it must have exponent at most

$p+h-1.$

Any selected reindeer with exponent at most that will only affect lower bits or contribute $0$. Since we are already below $x$, all such choices are valid. So they really do give a factor of $2^{pref[p+h-1]}$.

The forced prefix uses only exponents at least $p+h$, so there is no overlap with those free lower choices. Nice and clean.

Updates

We only store cnt[0..60] and the total number of reindeer $N$.

For add/remove queries, update one count and $N$.

For type 3 x:

1. Build prefix counts pref[i]=cnt[0]+...+cnt[i].
2. Scan bits from $60$ to $0$ as above.
3. Let less be the number of subsets with capacity $<x$.
4. Print

$2^N-less \pmod {998244353}.$

The empty subset has capacity $0$, and since every query has $x\ge1$, subtracting all subsets with capacity $<x$ automatically removes it. No awkward special case. We love when the math cleans up after itself.

Complexity

Each query scans only $61$ bits and touches arrays of size $61$.

So the complexity is

$O(61)$

per query, with $O(61)$ memory besides precomputed powers and inverses. That is easily fine for $3\cdot 10^5$ queries.