题解：CF2182F2-Christmas-Reindeer-hard-version
前言
精神状态 be like：
鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿鹿……
题意简述
先给你 只鹿，每只有能力值为 ，再给你 次询问，询问有三种。
- 添加一只能力值为 的鹿（）。
- 移除一只能力值为 的鹿（）。
- 记 为一群鹿的能力值的列表，将 按单调不增顺序排序，则该鹿群的总承载量为 ，求有多少个选择鹿群的方案使得这群鹿承载量不小于 （）。
保证 ，。
Solution
我们只关心鹿的能力值，初始鹿和一二类型操作可以用桶来记录，桶的大小与 值域一致。
现在只需考虑如何数数（回答询问 3）。
记 表示能力值为 的鹿的数量， 为当前仍需要的承载量。
考虑从大到小枚举能力值为 的鹿，发现若选择当前鹿后总承载量就不小于 ，那么剩下的能力值更小的鹿可以随便选，即 种方案，所以重点在前面能力值更大这一部分的方案数，以及能力值为 的鹿的选择方案。
引理：若选择一只能力值为 的鹿产生的贡献小于 ，但严格大于 ，则当前这只鹿必选。
:::info[证明]{open}
设现在的系数为 ，则当前这只鹿贡献为 （注意到 是非负整数所以 ，就不用向下取整）。
下只鹿的贡献最大为 ，再往后同理。
又因为这个数列显然长度有限，往后可能的最大贡献和一定小于 ，所以如果不选能力值为 的鹿，那么贡献和就一定小于 ，因此一定小于 ，一定没有合法的方案。
:::
所以，根据引理，我们发现当前的鹿要么「贡献不小于 」，要么「贡献小于 ，但严格大于 」，否则就没有可行方案了。
我们现在设计这样一个流程（记权值系数为 ，前面鹿的方案数为 ）：
检查当前鹿贡献是否小于 且严格大于 且这种鹿已选的数量不到 。若是，选鹿，令 ，；若否，则进入第二步。
检查当前鹿是否还有剩余且贡献不小于 ，若是，记当前这种鹿选了 只，答案加上（前面选鹿的方案数）（在 只中至少选 只的方案数） ；若否，则进入第三步。
记当前这种鹿选了 只，令 。处理 ，返回第一步。
注意到，第一步最多执行 次（每次都至少让 减半），第二步最多执行 61 次，但第二步中「计算在 只中至少选 只的方案数」是 的，也就是说每次询问 3 的最大执行次数在 次，最后总计时间复杂度在 1e9 这个数量级，不可接受，考虑预处理。
记计算在 只中至少选 只的方案数为 ，注意到有如下递推式：，边界为 。
可以通过其现实意义理解， 表示从 个中选至少 个，再添一个的方案数， 表示从 个中选至少 个，添的一个不选的方案数，加起来就是 。
又发现实际 ，，所以直接预处理 ， 的 即可，复杂度可以接受。
时间复杂度
记 和 的值域为 。
预处理：。
询问：单次最大 ，共计 。
整体 。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
| #include <bits/stdc++.h>
using namespace std;
namespace FastIO
{
template <typename T>
inline void read(T &x)
{
short neg = 1;
char ch;
while (ch = getchar(), !isdigit(ch))
if (ch == '-')
neg = -1;
x = ch - '0';
while (ch = getchar(), isdigit(ch))
x = (x << 3) + (x << 1) + (ch ^ '0');
x *= neg;
}
template <typename T, typename... Args>
inline void read(T &x, Args &...args)
{
read(x);
read(args...);
}
template <typename T>
inline void read(T *begin, T *end)
{
unsigned len = end - begin;
for (unsigned i = 0; i < len; i++)
read(*(begin + i));
}
template <typename T>
inline void write(T x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
template <typename T, typename... Args>
inline void write(T x, Args... args)
{
write(x);
putchar(' ');
write(args...);
}
template <typename T>
inline void write(T *begin, T *end)
{
unsigned len = end - begin;
for (unsigned i = 0; i < len; i++)
write(*(begin + i)), putchar(' ');
}
}
using namespace FastIO;
typedef long long LL;
typedef unsigned long long uLL;
const LL mod = 998244353;
LL n, m;
LL sum[65], cnt[65];
LL fac[600005], inv[600005], ifac[600005];
LL u[600005][65];
void init()
{
u[0][0] = 1, fac[0] = 1, inv[0] = 1, ifac[0] = 1;
u[1][0] = 2, u[1][1] = 1, fac[1] = 1, inv[1] = 1, ifac[1] = 1;
for (int i = 2; i <= 600000; i++)
{
inv[i] = (mod - mod / i) * (inv[mod % i]) % mod;
fac[i] = fac[i - 1] * i % mod;
ifac[i] = ifac[i - 1] * inv[i] % mod;
u[i][0] = u[i - 1][0] * 2 % mod;
for (int j = 1; j <= min(i, 60); j++)
{
u[i][j] = (u[i - 1][j - 1] + u[i - 1][j]) % mod;
}
}
}
LL C(int n, int m)
{
if (m > n || m < 0)
return 0;
if (m == n || m == 0)
return 1;
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
void solve()
{
read(n, m);
int xi;
for (int i = 1; i <= n; i++)
{
read(xi);
cnt[xi]++;
}
LL op, x;
while (m--)
{
read(op, x);
if (op == 1)
cnt[x]++;
else if (op == 2)
cnt[x]--;
else
{
sum[0] = cnt[0];
for (int i = 1; i <= 60; i++)
sum[i] = sum[i - 1] + cnt[i];
int cur = 0;
LL ans = 0, pre = 1;
for (int i = 60; i >= 0; i--)
{
int now = 0;
while (now < cnt[i] && (((1ll << i) >> cur) > (x >> 1) && ((1ll << i) >> cur) < x))
{
x -= ((1ll << i) >> cur);
cur++;
now++;
}
if (now < cnt[i] && ((1ll << i) >> cur) >= x)
{
ans = (ans + (pre * (i ? u[sum[i - 1]][0] : 1) % mod * u[cnt[i]][now + 1])) % mod;
}
pre = pre * C(cnt[i], now) % mod;
}
write(ans);
putchar('\n');
}
}
return;
}
signed main()
{
init();
solve();
return 0;
}
|
