← 返回题单
题单练习 动态规划的优化
← 上一题 下一题 →

A7069 | Welcome24ever 和 MEX

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给定一个多重集（或把数组当成多重集）$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$ 个或很多个），剩下元素保持原相对顺序得到的序列。

输入格式

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

输出格式

对每个测试用例输出一行一个整数，表示答案对 $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
C++ 编辑器
输入
输出