CF-Edu-186-F1. Christmas Reindeer (easy version/hard version)

思路讲解

这是问题的简单版本。版本之间唯一的区别在于$n$和$m$的上限。在这个版本中，$n \le 500$且$m \le 500$。

你有一群$n$只圣诞驯鹿。第$i$只驯鹿的力量是$2^{c_i}$。

$k$只圣诞驯鹿组的运载能力计算如下：

• 驯鹿的力量按非递增顺序排序。我们把排序后的力量列表表示为$c'_1, c'_2, \dots, c'_k$，其中$c'_i\ge c'_{i+1}$；

• 然后，这群驯鹿的运载能力等于$c'_1 + \lfloor\frac{c'_2} {2}\rfloor + \lfloor\frac{c'_3} {4}\rfloor + \dots + \lfloor\frac{c'_k} {2^{k - 1}}\rfloor$。

注意，一些驯鹿可能对群体的运载能力没有贡献。

你需要处理三种类型的查询：

1. 添加一只力量为$2^x$的驯鹿到群中；

2. 从驯鹿群中移除一只力量为$2^x$的驯鹿；

3. 计算选择一些驯鹿（可能是所有）的方式数量，使得所选群体的运载能力至少为$x$。

如果群中有多只力量相同的驯鹿，它们被视为不同的驯鹿。例如，如果你有两只力量各为$1$的驯鹿，并且需要计算选择运载能力至少为$1$的群体的方式数量，那么有$3$种选择方式：选择第一只驯鹿，选择第二只驯鹿，或者选择它们两只。

---

思路讲解

这个全部都和 2 的次方有关系，我们不自觉的就会往二进制的方向想，但是问题在于，我们如何处理这个进位问题？

等等，有没有一种可能，我们不需要处理进位问题？$c'_1 + \lfloor\frac{c'_2}{2}\rfloor + \lfloor\frac{c'_3}{4}\rfloor + \dots + \lfloor\frac{c'_k}{2^{k - 1}}\rfloor$，由于这个 C 是非严格递减的，即便在全部相等的前提下，因为右移作用越来越强烈，其为 1 的地方也在不断往后移动，因此，其实不会发生进位。

那么既然不会发生进位，第一个堵点就消失了。

接着我们就手玩一下样例，用组合计数的方式解决一下这个问题。

注意，在设计这个计数算法的过程当中，尽量让每层保持独立，即该层只考虑选了该层的数字的情况，这样子前面的数字因为选了他们的组合已经选过了，就不用考虑了，会轻松一点。

不过这道题目能不能做到这一点呢？就让我们看看解法吧。（是可以的，但需要一个关键观察，特别是对于前缀相等情况）

为了方便描述这个过程，令 $freq_i$ 为输入数组中 i 的频数，$pre_i$ 为 i 位置前（包括自己）最晚的 1 出现位置（描述的是查询数字 x），$rem$ 这个数字指的是 i 之后所有的数字的频数之和。

答案 $ans\gets0$，等于（前缀相同）情况下的辅助统计量 $eqAns\gets1$。

其实，在做这道题目的时候，我也不止一次的想过，要是这道题目是 $>x$ 就好了。那所以说，我们为什么不这么做呢？$eqAns$ 维护等于情况，$ans$ 维护严格大于情况，最后 $ans\gets ans+eqAns$ 不就行了？

从高到低遍历，遇到一位 $freq_i>0$，有这么几种情况。

• Case 1：$i=pre_i$
  • 如果 $freq_i=1$，不需要进行任何操作。
  • 如果 $freq_i>1$，这个是最复杂的情况。面对这种情况，我还想过记忆化搜索，dp 等等，以解决这个问题，不过最后发现，其实都不用，只需要一个关键观察：即需要选择多少个 i 达到这个等于状态是唯一确定的。你需要选择的数量，就是（自这位开始的）连续 1 的数量，令其为 $\text{conti1}$。
    • 首先，如果你选择的数量超过了（自这位开始的）连续 1 的数量，那么你就已经超过了，超过的时候至少要驻守 $\text{conti1}+1$ 个，才能保证超过，当然，除了 $i-\text{conti1}=0$ 的特殊情况，这种特殊情况因为相等，所以只能更新 $eqAns$***。***当然，写出这里的统计式子需要有这么一个想法，就是把 $rem$ 和这个前面这部分分开来看。

$$i-\text{conti1}=0:eqAns\gets eqAns\times(\sum^{freq_i}_{j=\text{conti}}C_{freq_i}^{j})\times2^{rem} \\ i-\text{conti1}>0:ans\gets ans+eqAns\times(\sum^{freq_i}_{j=\text{conti+1}}C_{freq_i}^{j})\times2^{rem} \\ eqAns\gets eqAns \times C^{conti1}_{freq_i}$$

  因为 $\text{conti1}$ 很小，这个式子中间的求和可以用从全组合减去东西的方式优化，达到 $O(W) $ 级别。
- 那么，你如果选的数量小于连续 1 的数量，那么你直接就没有资格相等（以第一个样例为例，$2\ 1\ 1$，只能凑出 $5={(101)}_{2}$，没法凑出 $6={(110)}_{2}$ 这样连续的 1，因为 2 的数量没有达到这个连续段 1 的数量要求）。因此如果 i 的频数小于连续的 1 的数量，直接 break 整个计数过程，并且使得  $eqAns\gets 0$。
- 当然，我们还需要进行**全局右移操作**，即：

auto right_move=[&](ll step) {   //  传入参数 step = conti1
    for (int j=1;j<i;++j) {
        freq[max(0ll,j-step)]+=freq[j];
        freq[j]=0;
    }
};

• Case 2：$i>pre_i$
  注意，思路要清楚，$ans$ 一定要保证这个答案 $>x$，$eqAns$ （统计的）一定要保证前缀严格相等。还是一样，$i=0$ 代表运载能力为 0，只能更新 $eqAns$。$i>0$ 的时候更新 $ans$ 从 $j=1$ 开始是因为至少你要选一个才超过是吧。

$$i=0:eqAns\gets eqAns \times 2^{freq_i} \\ i>0:ans\leftarrow ans+eqAns\times(\sum^{freq_i}_{j=1}C_{freq_i}^{j})\times2^{rem}$$

如果说 $freq_i=0$，需要进行这个合法性检验，即如果 $i=pre_i$，直接 break 整个计数过程，并且使得 $eqAns\gets 0$。

⚠️ 注意：我们从高到低遍历，我们要遍历到 -1（就是代表这些驼鹿的运载能力归零了），因此，我们会给整个系统加一个偏移量，0 代表指数为 -1，1 代表为 0，以此类推。

⚠️ 注意：所有的 break 之前，都要使得 $eqAns\gets 0$。

AC代码

AC，解法可以通过 F2。

https://codeforces.com/contest/2182/submission/357349404

源代码

/**
 * Problem: F1. Christmas Reindeer (easy version)
 * Contest: Educational Codeforces Round 186 (Rated for Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2182/problem/F1
 * Created: 2026-01-11 11:57:55
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>

#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */
namespace Comb {
    // 组合数加逆元，依赖于这个MAXN（初始化）
    vector<ll> frac, infrac;
    int ln = 1;
    bool initialized = false;

    inline ll binpow(ll a, ll k) {
        ll res = 1;
        a %= mod;
        while (k > 0) {
            if (k & 1) res = (res * a) % mod;
            a = (a * a) % mod;
            k >>= 1;
        }
        return res;
    }

    void Comb(int n) {
        ln = n;
        frac.assign(n + 5, 1);
        infrac.assign(n + 5, 1);
        for (int i = 1; i <= ln; ++i) {
            frac[i] = (frac[i - 1] * i) % mod;
        }
        infrac[ln] = binpow(frac[ln], mod - 2);
        for (int i = ln - 1; i >= 0; --i) {
            infrac[i] = (infrac[i + 1] * (i + 1)) % mod;
        }
    }

    inline ll CC(ll k, ll n) {
        if (k < 0 || k > n) {
#ifdef LOCAL
            cerr << "CC 组合数传入参数不合法，可能是传入顺序错了\n";
#endif
            return 0; // Return 0 if k is out of range [0, n]
        }
        if (!initialized) {
            Comb(MAXN);
            initialized = true;
        }
        ll res = frac[n];
        res = (res * infrac[n - k]) % mod;
        res = (res * infrac[k]) % mod;
        return res;
    }

    inline ll PP(ll k, ll n) {
        if (k < 0 || k > n) {
#ifdef LOCAL
            cerr << "PP 排列数传入参数不合法，可能是传入顺序错了\n";
#endif
            return 0;
        }
        if (!initialized) {
            Comb(MAXN);
            initialized = true;
        }
        ll res = frac[n] * infrac[n - k];
        res %= mod;
        return res;
    }
}

using namespace Comb;

void Solve() {
    ll N, M;
    cin >> N >> M;
    vector<ll> C(N);
    vector<ll> freq(65);
    for (int i = 0; i < N; ++i) {
        cin >> C[i];
        freq[C[i] + 1]++;
    }
    vector<ll> pow_2(N + M +2);
    pow_2[0] = 1;
    for (int i = 1; i <= N+M; ++i) {
        pow_2[i] = pow_2[i - 1] << 1;
        pow_2[i] %= mod;
    }
    for (int _ = 1; _ <= M; ++_) {
        ll op, x;
        cin >> op >> x;
        if (op == 1) {
            freq[x + 1]++;
            continue;
        }
        if (op == 2) {
            freq[x + 1]--;
            continue;
        }
        x <<= 1;
        bitset<70> bix(x);
        vector<ll> pre_1(70, -2);
        for (int i = 0; i <= 65; ++i) {
            if (bix[i]) {
                pre_1[i] = i;
            } else {
                pre_1[i] = (i - 1 < 0 ? -2 : pre_1[i - 1]);
            }
        }
        /*******下面是核心计数部分***********/
        vector<ll> freq_back_up = freq;
        ll ans = 0, eqAns = 1;
        bool reachEq=false;
        for (int i = 63; i >= 0; --i) {
            if (freq[i] == 0) {
                if (i == pre_1[i]) {
                    eqAns=0;
                    break;
                }
                continue;
            }

            /**********辅助函数***********/
            auto cnt_rem = [&]() {
                ll rem = 0;
                for (int j = 0; j < i; ++j) {
                    rem += freq[j];
                }
                return rem;
            };

            auto cnt_conti1 = [&]() {
                ll res = 0;
                for (int j = i; j >= 0; --j) {
                    if (bix[j]) {
                        ++res;
                        pre_1[j] = -2;
                    } else {
                        break;
                    }
                }
                return res;
            };
            auto right_move = [&](ll step) {
                for (int j = 1; j < i; ++j) {
                    freq[max(0ll, j - step)] += freq[j];
                    freq[j] = 0;
                }
            };
            auto cal_comb_sum = [&](ll st) {
                ll res = pow_2[freq[i]];
                for (int j = 0; j < st; ++j) {
                    res -= CC(j, freq[i]);
                    res %= mod;
                }
                return res;
            };
            // auto is_spec=[&](ll rem) {
            //     if (i<=lowbit && reachEq && rem==0) {
            //         return true;
            //     }
            //     return false;
            // };
            /**********************/

            if (i > pre_1[i]) {
                ll rem = cnt_rem();
                ll lans = 0;
                if (i==0) {
                    eqAns*=cal_comb_sum(0);
                    eqAns%=mod;
                }else if (i>=1){
                    // 只要不是 0，都一定有贡献能力（完全不选的情况让后面的值考虑）
                    lans=cal_comb_sum(1);
                    lans*=pow_2[rem];
                    lans%=mod;
                    lans *= eqAns;
                    lans %= mod;
                    ans += lans;
                    ans %= mod;
                }
            } else if (i == pre_1[i]) {
                /******等于的情况，最复杂******/
                ll conti1 = cnt_conti1();
                if (conti1 > freq[i]) {
                    eqAns=0;
                    break;
                }
                right_move(conti1);
                ll rem = cnt_rem();
                if (conti1 == freq[i] && i-conti1>=1) {
                    continue;
                }
                ll lans = 0;
                ll upEq=eqAns;
                if (i-conti1<1) {
                    eqAns*=cal_comb_sum(conti1);
                    eqAns %= mod;
                } else {
                    lans = cal_comb_sum(conti1 + 1);
                    eqAns *= CC(conti1, freq[i]);
                    eqAns %= mod;
                }
                lans *= pow_2[rem];
                lans %= mod;
                lans *= upEq;
                lans %= mod;
                ans += lans;
                ans %= mod;
            }
        }
        ans+=eqAns;
        ans %= mod;
        if (ans < 0) ans += mod;
        cout << ans << "\n";
        swap(freq, freq_back_up);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // cin >> lT;
    // while(lT--)
    Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2182/submission/357349404

3 3
2 1 1
1 2
2 1
3 5

6 1
3 3 0 2 4 3
3 21

3 1
3 4 4
3 19


*/

---

心路历程（WA，TLE，MLE……）

一开始的算法得出来的答案不太对，因为计数条件和题目规定有不同，题目的 C 数组是排好序的，因此就不在乎顺序了，求的就是组合数。

• 如果 $freq_i>1$，还好办吗？我们先想一种，即 $ans\leftarrow ans+2^{rem}\times freq_i$，毕竟有 $freq_i$ 种选择嘛，这种自然是没什么问题。但是，选了一个 i 以后，其他的 i 我们直接放任不管吗？这是不行的，我们还需要进行右移操作，即 $freq_{i-1}\gets freq_{i-1}+freq_i-1$（先右移，再统计这个 $rem$ 数量）。

• 如果 $freq_i>1$，这个是最复杂的情况，我们需要求出来新的 $eqAns$。$eqAns\gets eqAns \times freq_i$，然后，我们要进行右移操作，我们进行的是全局右移操作，即对 $\forall\ i'< i$，$freq_{i'-1}\gets freq_{i'-1}+freq_{i'}$，$freq_{i-1}\gets freq_{i-1}+freq_i-1$。

• Case 2：$i=pre_i$
  • 如果 $freq_i=1$，不需要进行任何操作。
  • 如果 $freq_i>1$，这个是最复杂的情况。我们发现，这里，如果我们选了第一个数，可以下放 $freq_{i}-1$ 个数字到 $freq_{i-1}$，但是选了第二个数字以后，只能下放 $freq_{i}-2$ 个数字到 $freq_{i-1}$，这种下放，好像不能用公式法做出来，难道每一个都要重新算吗？
    • 其实我们会有一个感觉，就是好像，这个是可以记忆化搜索，或者说是 dp 的。可以发现我们的这个状态由这几个因素决定：
      
    • 其实我们会发现这个 dp 和询问的 x 没什么关系，可以放在一起做？不过你说还有操作增删操作？呃，这个确实是一个问题，不过由于整个东西是离线的，我们可以得到每个位置的 $freq_i$ 的最大值，按照这个 dp，就不会出现问题了。
    • 不过还有一个问题，就是如何将查询做到 $O(1)$ 呢？其实这个的话前缀和即可。不过折腾来，

⚠️ 注意：注意有限右移操作和全局右移操作。

那么这个上面是我们脑内模拟了一下这个过程，得出来的计数结论，我们实现一下，看看对不对？

哈哈，我们会发现，这样子操作，得出来的答案不对，这是为什么呢？。

以这个第一个样例的第一个询问为例，我们会发现，其实这个答案并不在乎顺序。

那我们的计算要怎么样搞？其实，我们发现我们上面的思路还是比较混乱的，即有的时候认为是组合，有的时候又认为是排列。

不过，我们发现，题目中的 $c'_i\ge c'_{i+1}$ 是非常重要的，这意味着，只要是为了这个相等作用，无论

⚠️ 注意：我们从高到低遍历，我们要遍历到 -1（就是代表这些驼鹿的运载能力归零了），因此，我们会给整个系统加一个偏移量。

$$rem=0:ans\gets ans+eqAns\times((2^{rem+freq_{i}-\text{conti1}}+\cdots+2^{rem})+ \\ (2^{rem+freq_{i}-\text{conti1}-1}+\cdots+2^{rem})+\cdots+2^{rem}) \\ rem≠0:ans\gets ans+eqAns\times((2^{rem+freq_{i}-\text{conti1}-1}+\cdots+2^{rem})+ \\ (2^{rem+freq_{i}-\text{conti1}-2}+\cdots+2^{rem})+\cdots+2^{rem})$$

• Case 1：$i>\text{MSB}$（MSB 即查询数字 x 最大二进制位的位数）
  • 如果 $freq_i=1$，那么好办，直接 $ans\leftarrow ans+2^{rem}$ 即可。
  • 如果 $freq_i>1$，还好办吗？这里需要有这么一个想法，就是把 $rem$ 和这个前面这部分分开来看，即：

$$ans\leftarrow ans+2^{rem+freq_{i}-1}+2^{rem+freq_{i}-2}+ \cdots+ 2^{rem}$$

这个式子这样子理解，首先，这个数组 C 是倒序排序的，即 $c'_i\ge c'_{i+1}$，因此，选了排在第一个的数，就有 $2^{rem+freq_{i}-1}$ 种组合（全组合的这个公式），选了排在第二个的数，就只有 $2^{rem+freq_{i}-2}$ 种组合了（没法选第一个数），一次类推，就得到了这个式子。之后，我们就当 i 这个数字不存在就行了。