CF2182F | Ficon's Paper

减法的取模运算要注意。
cout << endl 频繁刷新缓冲区会导致 TLE
能预处理的尽量预处理，避免 TLE

CF2182F

设 $c$ 值为

在第 $k$ 位选一个 $c$ 值大的一定比从 $k$ 开始全部选 $c - 1$ 要优：

第 $i$ 个位置对承载能力产生的贡献为： $\frac{c_{i}}{2^{i - 1}}$

后面全选的贡献是 $\frac{c}{2^{i-1}}-\frac{c-1}{2^{k-1}}$ ，严格小于 $\frac{c}{2^{i-1}}$

这里可以类比 $2^i-1=2^0+2^1+2^2+2^3+\dots+2^{i-1}$ 的推导，不详细展开。

我们先来看看对于每个 3 查询，让负载能力恰好等于 $x$ 有多少种方式：

设 $r_i$ 为使负载能力恰好为 $x$ 所需要的 $i$ 类型的鹿， $d_i$ 为当前所有的 $i$ 类型的鹿。

那么总答案就是 $\prod_{i=0}^{60} \binom{d_{i}}{r_{i}}$

怎么求 $r_{i}$ ？

将 $x$ 二进制拆分，从 $x$ 的最高位向最低位开始遍历，如果这一位是 $1$ ，那么就需要用当前这一位的位次加上已经选择的鹿的数量的类型。

      int lead = 63 - __builtin_clzll(x);
      int cnt = 0;
      vi r(61);
      for (int i = lead; i >= 0; i--) {
        int digit = (x >> i) & 1;
        if (digit) {
          r[i + cnt]++;
          cnt++;
        }
      }

可以用 __builtin_clzll(x) 来得到一个数的前导零个数，从而得到这个数的二进制下的长度。

考虑负载能力严格大于 $x$ 的情况：

由上面的条件可以知道，选择一个大的比后面全选小的还要优。这就说明：一旦前面多选了一个大的，那么后面就可以随便选了。

所以枚举这个多选的那个类型 $i$ ， $[i+1, 60]$ 都需要恰好选 $r_i$ 个， $i$ 位选至少 $r_i+1$ 个， $[0,i-1]$ 随便选，用 $way_i$ 表示第 $i$ 位多选的总方案数。

$\text{way}_i = \underbrace{\left( \prod_{j=i+1}^{60} \binom{f_j}{r_j} \right)}_{\text{Part 1: 高位完全匹配}} \times \underbrace{\left( \sum_{k=r_i+1}^{f_i} \binom{f_i}{k} \right)}_{\text{Part 2: 当前位胜出}} \times \underbrace{\left( 2^{\sum_{j=0}^{i-1} f_j} \right)}_{\text{Part 3: 低位任意选择}}$

枚举 $i$ 从 60 到 0，第一项可以边遍历边计算，第二部分可以暴力算，但是不足以通过 hard version，第三部分可以维护一个后缀和即可。

思考一下复杂度，外层一个 $m$ ，内层 $\log x\times N + \log x$ ，发现主要瓶颈出现在计算第二部分，考虑优化。

我们发现组合数的性质之一是： $\binom{k}{0}+\binom{k}{1}+\binom{k}{2}+\binom{k}{3}+\dots+\binom{k}{k}=2^k$ ，而 $r_i$ 很小，最大也就是 $\log x=60$ ，所以我们可以采用补集的思想，计算 $2^k-\sum_{0}^{r_{i}}$ 即可，这样可以将复杂度优化到 $\log x$ ，足以通过 hard version

需要注意的是，组合数在 hard version 没办法 $N^2$ 预处理。 $2^k$ 需要预处理。

代码示例：

#include <bits/stdc++.h>
#define ve vector
#define fi first
#define se second
using namespace std;
using ll = long long;
using vi = vector<int>;
using vii = vector<vector<int>>;
const ll MOD = 998244353;
int n, m;
ve<ll> fac, ifac, pw2;

int qp(int x, int y) {
  int res = 1;
  for (int t = x; y; y >>= 1, t = 1ll * t * t % MOD)
    if (y & 1)
      res = 1ll * res * t % MOD;
  return res;
}

ll qpow(ll x, ll y) {
  if (!y)
    return 1;
  ll z = qpow(x, y >> 1);
  z = z * z % MOD;
  if (y & 1)
    z = z * x % MOD;
  return z;
}

void init() {
  int N = n + m + 7;
  fac.resize(N), ifac.resize(N), pw2.resize(N);
  fac[0] = 1;
  for (int i = 1; i < N; i++) {
    fac[i] = fac[i - 1] * i % MOD;
  }
  pw2[0] = 1;
  for (int i = 1; i < N; i++) {
    pw2[i] = pw2[i - 1] * 2 % MOD;
  }
  ifac[N - 1] = qpow(fac[N - 1], MOD - 2);
  for (int i = N - 2; i >= 0; i--) {
    ifac[i] = ifac[i + 1] * (i + 1) % MOD;
  }
}

ll Co(int x, int y) {
  if (x < y || y < 0)
    return 0;
  return fac[x] * ifac[y] % MOD * ifac[x - y] % MOD;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  init();
  vi c(n);
  vi d(61);
  for (int i = 0; i < n; i++) {
    cin >> c[i];
    d[c[i]]++;
  }
  while (m--) {
    int opt;
    ll x;
    cin >> opt >> x;
    if (opt == 1) {
      d[x]++;
      n++;
    } else if (opt == 2) {
      d[x]--;
      n--;
    } else if (opt == 3) {
      int lead = 63 - __builtin_clzll(x);
      int cnt = 0;
      vi r(61);
      for (int i = lead; i >= 0; i--) {
        int digit = (x >> i) & 1;
        if (digit) {
          r[i + cnt]++;
          cnt++;
        }
      }
      ll ans = 0;
      int sum = n;
      ll P1 = 1;
      for (int i = 60; i >= 0; i--) {
        sum -= d[i];
        if (i != 60) {
          P1 = P1 * Co(d[i + 1], r[i + 1]) % MOD;
        }
        ll P2 = pw2[d[i]];
        for (int j = 0; j <= r[i]; j++)
          P2 = (P2 - Co(d[i], j) + MOD) % MOD;
        ll P3 = pw2[sum];
        ans = (ans + ((P1 * P2 % MOD) * P3 % MOD)) % MOD;
      }
      ans = (ans + P1 * Co(d[0], r[0]) % MOD) % MOD;
      cout << ans << '\n';
    }
  }
  return 0;
}