A16789. Christmas Reindeer (easy version)
编程题
提高+/省选-
知识点
题目描述
这是本题的简单版本。不同版本之间唯一的区别在于 $n$ 和 $m$ 的上界。在本版本中，$n \leq 500$ 且 $m \leq 500$。
你有 $n$ 只圣诞驯鹿，第 $i$ 只驯鹿的力量为 $2^{c_i}$。
一组 $k$ 只圣诞驯鹿的负重能力的计算方式如下：
- 首先将这些驯鹿按力量从大到小排序。排好序的力量记作 $c'_1, c'_2, \dots, c'_k$，其中 $c'_i \geq 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$ 种方法：可以只选第1只，或只选第2只，或两只都选。
你有 $n$ 只圣诞驯鹿，第 $i$ 只驯鹿的力量为 $2^{c_i}$。
一组 $k$ 只圣诞驯鹿的负重能力的计算方式如下：
- 首先将这些驯鹿按力量从大到小排序。排好序的力量记作 $c'_1, c'_2, \dots, c'_k$，其中 $c'_i \geq 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$ 种方法：可以只选第1只，或只选第2只，或两只都选。
输入格式
第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 500$）——初始驯鹿的数量和查询的数量。
第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$0 \leq c_i \leq 60$），表示每只驯鹿的力量，具体来说，第 $i$ 只驯鹿的力量为 $2^{c_i}$。
接下来 $m$ 行，每行对应一个查询，格式如下：
- $1\ x$（$0 \leq x \leq 60$）——向驯鹿群中添加一只力量为 $2^x$ 的驯鹿；
- $2\ x$（$0 \leq x \leq 60$）——从驯鹿群中移除一只力量为 $2^x$ 的驯鹿；
- $3\ x$（$1 \leq x \leq 10^{18}$）——计算有多少种选法可以从驯鹿群里选出若干只组成一组，使该组负重能力至少为 $x$。
输入额外约束：对于每个类型为 $2$ 的查询，当前驯鹿群内至少有一只力量为 $2^x$ 的驯鹿。
第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$0 \leq c_i \leq 60$），表示每只驯鹿的力量，具体来说，第 $i$ 只驯鹿的力量为 $2^{c_i}$。
接下来 $m$ 行，每行对应一个查询，格式如下：
- $1\ x$（$0 \leq x \leq 60$）——向驯鹿群中添加一只力量为 $2^x$ 的驯鹿；
- $2\ x$（$0 \leq x \leq 60$）——从驯鹿群中移除一只力量为 $2^x$ 的驯鹿；
- $3\ x$（$1 \leq x \leq 10^{18}$）——计算有多少种选法可以从驯鹿群里选出若干只组成一组，使该组负重能力至少为 $x$。
输入额外约束：对于每个类型为 $2$ 的查询，当前驯鹿群内至少有一只力量为 $2^x$ 的驯鹿。
输出格式
对于每一个类型为3的查询，输出一行一个整数，表示可行组数。由于答案可能很大，请输出该数对 $998244353$ 取模后的结果。
输入输出样例
输入 #1
3 7 2 1 1 3 5 3 6 1 2 3 6 3 5 2 1 3 5
输出 #1
3 0 4 10 4
说明/提示
让我们来看第一个样例。初始时，有三只驯鹿，力量分别为 $4$、$2$、$2$。
- 第一次查询，需要计算负重能力至少为 $5$ 的组数。有三组可行：$\{1,2\}$（第1、2只驯鹿），$\{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只，现在只剩驯鹿1、3、4；
- 第七次查询，需要计算负重能力至少为 $5$ 的组数。可行的组有 $\{1,3\}$、$\{1,4\}$、$\{1,3,4\}$、$\{3,4\}$。
- 第一次查询，需要计算负重能力至少为 $5$ 的组数。有三组可行：$\{1,2\}$（第1、2只驯鹿），$\{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只，现在只剩驯鹿1、3、4；
- 第七次查询，需要计算负重能力至少为 $5$ 的组数。可行的组有 $\{1,3\}$、$\{1,4\}$、$\{1,3,4\}$、$\{3,4\}$。