CF-Edu-186-F1. Christmas Reindeer (easy version/hard version) · znzryb
## 思路讲解
这是问题的简单版本。版本之间唯一的区别在于$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$的驯鹿到群中；
1. 从驯鹿群中移除一只力量为$2^x$的驯鹿；
1. 计算选择一些驯鹿（可能是所有）的方式数量，使得所选群体的运载能力**至少为**$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$。
- 当然，我们还需要进行**全局右移操作**，即：
```cpp
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](https://codeforces.com/contest/2182/submission/357349404)
::: 源代码
```cpp
/**
* 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 这个数字不存在就行了。