← 返回题目列表

Codeforces · 2030/E

E. MEX 最大化分数

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

假设我们将数组 $$$b$$$ 的元素划分为任意数量的 $$$k$$$ 个非空多重集 $$$S_1, S_2, \ldots, S_k$$$,其中 $$$k$$$ 是任意正整数。将 $$$b$$$ 的分数定义为 $$$\operatorname{MEX}(S_1)$$$$$^{\text{∗}}$$$$$$ + \operatorname{MEX}(S_2) + \ldots + \operatorname{MEX}(S_k)$$$ 在 $$$b$$$ 的所有可能分区上对于任何整数 $$$k$$$ 的最大值。

Envy 被赋予一个大小为 $$$n$$$ 的数组 $$$a$$$。因为他知道计算$$$a$$$的分数对你来说太容易了,所以他转而要求你计算$$$a$$$的所有$$$2^n - 1$$$非空子序列的分数总和。$$$^{\text{†}}$$$由于这个答案可能很大,请输出它对$$$998\,244\,353$$$取模。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i < n$$$) — 数组 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出答案,模 $$$998\,244\,353$$$。

示例

输入 #1

4
3
0 0 1
4
0 0 1 1
5
0 0 1 2 2
4
1 1 1 1

输出 #1

11
26
53
0

注意

在第一个测试用例中,我们必须考虑七个子序列:

- $$$[0]$$$:得分为$$$1$$$。
- $$$[0]$$$:得分为$$$1$$$。
- $$$[1]$$$:得分为$$$0$$$。
- $$$[0,0]$$$:得分为 $$$2$$$。
- $$$[0,1]$$$:得分为$$$2$$$。
- $$$[0,1]$$$:得分为$$$2$$$。
- $$$[0,0,1]$$$:得分为$$$3$$$。

在最后一个测试用例中,所有子序列的分数均为 $$$0$$$。