题解

思路

不必记录当前 MEX 的具体值，只需记录前缀中已出现的不同整数个数。

做法

设处理完前 $i$ 个位置后恰有 $j$ 个不同值的方案数为 $dp_j$。若 $S_{i+1}=1$，只能选当前 MEX，它是新值，所以当 $j\le M$ 时转移到 $j+1$。若 $S_{i+1}=0$，选已出现的值有 $j$ 种，不同值个数不变；在未出现且不是 MEX 的值中选择有 $M-j$ 种，不同值个数增加一。这两类选择已经穷尽所有合法的 $A_{i+1}$。

每层只依赖上一层，用滚动数组保存状态。

复杂度

不同值个数不会超过 $\min(N,M+1)$，因此时间复杂度为 $O(N\min(N,M+1))$，空间复杂度为 $O(\min(N,M+1))$。