MEX 计数：题解

思路

利用 MEX 单调性把每个前缀的允许值压成宽度不超过 $2k+1$ 的窗口；再把严格大于当前 MEX 的已出现值抽象化，仅记录其个数。最后用窗口内的级联转移一次生成全部 MEX 跳跃。

一、允许的 MEX 区间

设前缀 $a_1,\ldots,a_i$ 的 MEX 为 $m_i$。原限制等价于

$$\max(0,b_i-k)\le m_i\le \min(n,b_i+k).$$

MEX 随前缀延长只会增大，不会减小。因此可以把左端点替换为前缀最大值，把右端点替换为后缀最小值。记处理后的区间为 $[L_i,R_i]$。若某个 $L_i>R_i$，答案立即为 $0$。

每个区间的宽度不超过 $2k+1$，这是优化复杂度的关键。

二、抽象掉大于 MEX 的具体值

处理完若干个位置后，设当前 MEX 为 $m$。此时 $0,1,\ldots,m-1$ 一定出现过，$m$ 一定没有出现。再设已经出现过的、严格大于 $m$ 的不同数共有 $j$ 个。

暂时不记录这 $j$ 个数的具体数值，只按首次出现的先后顺序给它们抽象编号。定义

$$dp[j][m]$$

为当前抽象序列的方案数。

初始只有空序列，故 $dp[0][0]=1$。

做法

三、加入下一个数

从状态 $(j,m)$ 加入一个数，有三类转移。

1. 加入已经出现过的数

已经出现的不同数共有 $m+j$ 个，因此

$$ndp[j][m]\mathrel{+}=dp[j][m](m+j).$$

2. 加入一个新的、严格大于 $m$ 的数

这个新数先作为下一个抽象编号记录，具体取值留到最后统一分配，因此

$$ndp[j+1][m]\mathrel{+}=dp[j][m].$$

3. 加入当前 MEX $m$

加入 $m$ 后，MEX 会增大。设新 MEX 为 $y>m$，则 $m+1,m+2,\ldots,y-1$ 必须已经出现在那 $j$ 个抽象大数中。

令 $x=y-m-1$。从 $j$ 个抽象编号中选出并依次指定这 $x$ 个具体值的方案数为下降幂

$$P(j,x)=\frac{j!}{(j-x)!}.$$

于是

$$ndp[j-x][y]\mathrel{+}=dp[j][m]P(j,x).$$

只保留 $y\in[L_i,R_i]$ 的转移。

四、把 MEX 跳跃降为线性扫描

若对每个状态枚举全部 $y$，复杂度会多出一个 $O(k)$ 因子。

对于同一来源状态，先向最小合法的新 MEX 转移。之后若当前跳跃状态为 $(j,y)$，再把一个尚未指定具体值的抽象编号指定为 $y$，就得到

$$(j,y)\longrightarrow(j-1,y+1),$$

转移系数为 $j$。

因此按 $y$ 从小到大扫描整个允许区间，即可一次生成所有更大的新 MEX。每层只需处理 $O(nk)$ 个状态，总复杂度为

$$O(n^2k),$$

空间复杂度为

$$O(nk).$$

下降幂使用阶乘和逆阶乘在 $O(1)$ 时间内计算。

五、恢复抽象大数的具体取值

最终状态为 $(j,m)$ 时，可使用的具体大数是 $m+1,m+2,\ldots,n$，共有 $n-m$ 个。按抽象编号的首次出现顺序，为它们选择互不相同的具体值，有

$$P(n-m,j)$$

种方法。因此答案为

$$\sum_{m,j} dp[j][m]P(n-m,j)\pmod {998244353}.$$

复杂度

时间复杂度为 $O(n^2k)$，空间复杂度为 $O(nk)$。

六、正确性证明

引理 1

在固定状态 $(j,m)$ 下，未来转移只与 $j,m$ 有关，而与那 $j$ 个大数当前的具体取值无关。

证明。 小于 $m$ 的数全部已经出现，$m$ 没有出现。未来只有“重复已出现值”“首次出现一个大于 $m$ 的值”以及“填入 $m$ 并让 MEX 跳跃”三种行为。它们分别只需要知道已出现不同值总数 $m+j$、抽象大数个数 $j$，以及跳跃时要指定多少个抽象编号。故具体取值不影响转移。证毕。

引理 2

三类转移不重不漏地覆盖加入下一个元素的全部可能。

证明。 下一个元素要么已经出现，要么未出现。若未出现，它要么等于当前 MEX $m$，要么大于 $m$；小于 $m$ 的数都已经出现，不可能属于未出现情形。三类互斥且覆盖全部取值。各类系数分别是已出现值的个数、一个新的抽象编号，以及把必要抽象编号指定为连续具体值的下降幂，计数均正确。证毕。

引理 3

跳跃扫描产生的系数等于直接转移中的 $P(j,x)$。

证明。 从新 MEX $m+1$ 开始，每再提高一格，都从剩余抽象编号中选一个指定给新的必需具体值。连续提高 $x$ 格的乘积为 $j(j-1)\cdots(j-x+1)=P(j,x)$。证毕。

定理

算法输出恰好等于满足题目全部前缀约束的数组数量。

证明。 由引理 2，动态规划逐位置不重不漏地枚举所有抽象序列；每层只保留当前合法 MEX，故恰好满足全部前缀约束。由引理 1，抽象化不会丢失未来所需信息；由引理 3，优化后的跳跃与直接转移等价。最后用 $P(n-m,j)$ 为每个抽象编号恢复互异的合法具体值，每个原数组对应唯一的抽象序列与一次恢复，反之亦然。因此最终求和即为答案。证毕。

七、部分分方法

• 子任务 1：枚举全部 $(n+1)^n$ 个数组，逐前缀维护出现次数和 MEX。
• 子任务 2：仍使用上述抽象状态，但直接枚举每次跳到的新 MEX，复杂度 $O(n^2k^2)$，足以通过 $n\le100$。
• 子任务 3：使用跳跃扫描优化到 $O(n^2k)$。