题解

思路

加入一个新元素后，题目只关心新序列的 MEX 与新元素之差。合法序列可以按“尚未出现的最小值”及是否走过一次高一格的特殊状态分类，因此每个可能的 MEX 只需常数个状态。

做法

子任务 1：枚举下标子集

枚举所有非空下标子集，按下标顺序加入元素，维护出现集合并重新求 MEX；若某一步不满足条件就拒绝。复杂度为 $O(2^n n^2)$。

子任务 2：按出现集合 DP

当所有值不超过 $12$ 时，用二进制掩码表示当前子序列出现过哪些值。扫描原数组的每个元素 $x$，从旧状态选择“不取”或“取”；取后计算新掩码的 MEX，仅在 $|x-\mathrm{MEX}|\le1$ 时转移。复杂度为 $O(n2^{13})$。

子任务 3：两类 MEX 状态

设 ordinary[m] 表示第一类合法子序列数，special[m] 表示已经使用另一侧选择的第二类子序列数。空序列作为 ordinary[0]=1 的起点。扫描当前值 $x$ 时，只会影响下标 $x-1$ 与 $x+1$：

$$\begin{aligned} ordinary[x+1]&\leftarrow 2\,ordinary[x+1]+ordinary[x],\\ special[x+1]&\leftarrow 2\,special[x+1],\\ special[x-1]&\leftarrow 2\,special[x-1]+ordinary[x-1]\quad(x>0). \end{aligned}$$

右侧乘二表示当前 $x$ 可以取或不取且状态不变；跨状态加法表示当前元素第一次补出对应结构。最后把两类所有状态求和并减去空序列。

正确性证明

引理 1

对任意已经合法的子序列，加入 $x$ 后仍合法的可能状态只涉及 $x-1$ 与 $x+1$ 两个 MEX 相邻位置。

证明：新一步要求 $|x-\mathrm{MEX}|\le1$，且加入一个值只可能保持 MEX 或使它越过刚补齐的最小缺失值，因此除这两个相邻位置外不可能产生合法转移。证毕。

引理 2

三条转移不重不漏地统计所有选择当前下标后仍合法的子序列。

证明：对每个旧状态，当前下标只有不取和取两种选择。同类状态中允许重复取当前值，对应乘二；第一次补齐缺失值或进入另一侧结构，对应唯一的跨状态加项。不同项由“是否取当前下标”和旧状态类别区分，因此互不重叠；由引理 1，也没有其他合法情况。证毕。

定理

算法输出全部非空 MEX 正确子序列数。

证明：初始只含一个空序列。逐个下标应用引理 2 后，两类数组恰好包含当前前缀的全部合法子序列。最终求和包含空序列一次，减一后正好得到全部非空合法子序列。证毕。

复杂度

每个输入元素只更新常数个状态：

• 时间复杂度：$O(\sum n)$；
• 空间复杂度：$O(\max n)$。