CF2030E.MEXimize the Score

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

Envy 给你一个长度为 $n$ 的数组 $a$。由于他知道你计算 $a$ 的得分太容易了，因此他要求你计算 $a$ 的所有 $2^n - 1$ 个非空子序列的得分之和。由于答案可能很大，请你输出其对 $998\,244\,353$ 取模的结果。

$\operatorname{MEX}$（Minimum EXcluded number）是指在一组整数 $c_1, c_2, \ldots, c_k$ 中未出现的最小非负整数。例如，$\operatorname{MEX}([0,1,2,2]) = 3$，$\operatorname{MEX}([1,2,2]) = 0$。

一个序列 $x$ 是序列 $y$ 的子序列，如果 $x$ 可以通过从 $y$ 中删除若干（可能为零或全部）元素得到。

第一行包含一个整数 $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$ 取模。

在第一个测试用例中，我们需要考虑七个子序列：

• $[0]$：得分为 $1$。
• $[0]$：得分为 $1$。
• $[1]$：得分为 $0$。
• $[0,0]$：得分为 $2$。
• $[0,1]$：得分为 $2$。
• $[0,1]$：得分为 $2$。
• $[0,0,1]$：得分为 $3$。

因此，第一个测试用例的答案为 $1+1+2+2+2+3=11$。在最后一个测试用例中，所有子序列的得分均为 $0$。

由 ChatGPT 4.1 翻译