← 返回题目列表

Codeforces · 2182/F1

F1. 圣诞驯鹿(简易版)

中文机器翻译题面 查看原题

这是问题的简单版本。版本之间的唯一区别是 $$$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$$$ 的选择方法:选择第一只驯鹿、第二只驯鹿或两者都选择。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 500$$$) – 分别是鹿群中驯鹿的初始数量和查询数量。

第二行包含 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_n$$$ ($$$0 \le c_i \le 60$$$) 表示驯鹿群中驯鹿的强度:第 $$$i$$$ 驯鹿的强度为 $$$2^{c_i}$$$。

接下来的 $$$m$$$ 行采用以下格式之一描述查询:

  • $$$1$$$ $$$x$$$ ($$$0 \le x \le 60$$$) — 将一头强度等于 $$$2^x$$$ 的驯鹿添加到鹿群中;
  • $$$2$$$ $$$x$$$ ($$$0 \le x \le 60$$$) — 从鹿群中移除一头强度等于 $$$2^x$$$ 的驯鹿;
  • $$$3$$$ $$$x$$$ ($$$1 \le x \le 10^{18}$$$) — 计算从鹿群中选择一组驯鹿的方法数,使得所选组的承载能力至少为 $$$x$$$。

对输入的附加约束:每当给出 $$$2$$$ 类型的查询时,鹿群当前至少包含一头强度等于 $$$2^x$$$ 的驯鹿。

输出

对于第三种类型的每个查询,打印一个整数 - 从鹿群(可能是整个鹿群)中选择一组驯鹿的方法数量,使得所选组的承载能力至少为 $$$x$$$。因为它可能很大,所以打印它对 $$$998244353$$$ 取模。

示例

输入
复制

3 7
2 1 1
3 5
3 6
1 2
3 6
3 5
2 1
3 5

输出
复制

3
0
4
10
4

输入
复制

5 5
6 9 2 3 5
3 518
1 4
2 9
1 10
3 1016

输出
复制

12
32

输入
复制

5 20
56 58 31 56 57
3 584133699915613698
1 26
3 718934517698133644
1 43
3 853795525565803934
3 371128907885602007
1 54
1 25
3 12283451778216771
2 25
3 269837405423769340
1 0
3 81332884431075468
1 23
3 4256984962444022
3 668408003982766102
3 923410222653374550
3 340313743235311415
3 550166282440775769
3 445344499963496530

输出
复制

0
0
0
24
496
128
416
992
0
0
320
0
0

注意

让我们考虑第一个例子。最初,有三只驯鹿,其力量分别为 $$$4$$$、$$$2$$$ 和 $$$2$$$。

  • 在第一次查询时,你必须计算有多少种方法来选择一个承载能力至少为$$$5$$$的组。共有三个可能的组:$$$\{1, 2\}$$$(包含 $$$1$$$-st 和 $$$2$$$-nd 驯鹿的组)、$$$\{1, 2, 3\}$$$ 和 $$$\{1, 3\}$$$;
  • 在第二次查询时,你必须计算有多少种方法来选择一个承载能力至少为$$$6$$$的组。即使整个牛群的承载能力等于 $$$4 + \lfloor\frac{2}{2}\rfloor + \lfloor\frac{2}{4}\rfloor = 5$$$,因此没有合适的方法来选择群体;
  • 在第三次查询期间,添加了一头力量为$$$4$$$的驯鹿。我们将其表示为第 $$$4$$$ 驯鹿;
  • 在第四次查询期间,可能的组为 $$$\{1, 4\}$$$、$$$\{1, 2, 4\}$$$、$$$\{1, 3, 4\}$$$ 和 $$$\{1, 2, 3, 4\}$$$;
  • 在第五次查询期间,有$$$10$$$可能的组;
  • 在第六次查询期间,一头强度为$$$2$$$的驯鹿被移除。假设这是第 $$$2$$$-nd 驯鹿,那么只剩下 $$$1, 3, 4$$$ 驯鹿;
  • 在第七次查询时,你必须计算选择承载能力至少为$$$5$$$的组的方法数。有四个可能的组:$$$\{1, 3\}$$$、$$$\{1, 4\}$$$、$$$\{1, 3, 4\}$$$、$$$\{3, 4\}$$$。