A7069. Welcome24ever 和 MEX
编程题
提高+/省选-
知识点
题目描述
给定一个多重集（或把数组当成多重集）$S$，定义 $\operatorname{MEX}(S)$ 为 **最小的未出现的非负整数**。例如：
- $\operatorname{MEX}([0,1,2,2]) = 3$
- $\operatorname{MEX}([1,2,2]) = 0$
现在把一个数组 $b$ 的所有元素划分成任意个 $k$ 个**非空多重集** $S_1,S_2,\ldots,S_k$（$k$ 为任意正整数）。定义 $b$ 的得分为所有划分方式中，下面这个值的最大值：
$\operatorname{MEX}(S_1)+\operatorname{MEX}(S_2)+\cdots+\operatorname{MEX}(S_k)$。
Welcome24ever 给你一个长度为 $n$ 的数组 $a$。你需要计算 $a$ 的所有 $2^n-1$ 个**非空子序列**的得分之和，并对 $998244353$ 取模。
子序列的定义：从 $a$ 中删除若干元素（可以删除 $0$ 个或很多个），剩下元素保持原相对顺序得到的序列。
- $\operatorname{MEX}([0,1,2,2]) = 3$
- $\operatorname{MEX}([1,2,2]) = 0$
现在把一个数组 $b$ 的所有元素划分成任意个 $k$ 个**非空多重集** $S_1,S_2,\ldots,S_k$（$k$ 为任意正整数）。定义 $b$ 的得分为所有划分方式中，下面这个值的最大值：
$\operatorname{MEX}(S_1)+\operatorname{MEX}(S_2)+\cdots+\operatorname{MEX}(S_k)$。
Welcome24ever 给你一个长度为 $n$ 的数组 $a$。你需要计算 $a$ 的所有 $2^n-1$ 个**非空子序列**的得分之和，并对 $998244353$ 取模。
子序列的定义：从 $a$ 中删除若干元素（可以删除 $0$ 个或很多个），剩下元素保持原相对顺序得到的序列。
输入格式
第一行包含一个整数 $t$，表示测试用例数量，满足 $1 \le t \le 10^4$。
每个测试用例：
- 第一行包含一个整数 $n$，满足 $1 \le n \le 2 \cdot 10^5$；
- 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，满足 $0 \le a_i < n$。
保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。
每个测试用例：
- 第一行包含一个整数 $n$，满足 $1 \le n \le 2 \cdot 10^5$；
- 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，满足 $0 \le a_i < n$。
保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。
输出格式
对每个测试用例输出一行一个整数，表示答案对 $998244353$ 取模的结果。
输入输出样例
输入 #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
说明/提示
### 样例解释
以第一个测试用例 $a=[0,0,1]$ 为例，共有 $2^3-1=7$ 个非空子序列（注意：从不同位置选出的子序列算不同，即使数值一样）。
它们的得分分别是：
- 选第 1 个 $0$：$[0]$，得分 $1$
- 选第 2 个 $0$：$[0]$，得分 $1$
- 选 $1$：$[1]$，得分 $0$
- 选两个 $0$：$[0,0]$，得分 $2$
- 选第 1 个 $0$ 和 $1$：$[0,1]$，得分 $2$
- 选第 2 个 $0$ 和 $1$：$[0,1]$，得分 $2$
- 全选：$[0,0,1]$，得分 $3$
总和为 $1+1+0+2+2+2+3=11$
以第一个测试用例 $a=[0,0,1]$ 为例，共有 $2^3-1=7$ 个非空子序列（注意：从不同位置选出的子序列算不同，即使数值一样）。
它们的得分分别是：
- 选第 1 个 $0$：$[0]$，得分 $1$
- 选第 2 个 $0$：$[0]$，得分 $1$
- 选 $1$：$[1]$，得分 $0$
- 选两个 $0$：$[0,0]$，得分 $2$
- 选第 1 个 $0$ 和 $1$：$[0,1]$，得分 $2$
- 选第 2 个 $0$ 和 $1$：$[0,1]$，得分 $2$
- 全选：$[0,0,1]$，得分 $3$
总和为 $1+1+0+2+2+2+3=11$