MEX counting

_ANIG_ · 2023-10-18 22:02:33 · 个人记录

考虑什么会对 mex 产生影响。

要想改变 mex，要么把下面的空填满，要么在一个原有的 mex 下面挖一个空。

第二种操作看起来比第一种好维护。所以可以考虑倒序 dp。

考虑哪些状态是有用的。我们需要

用 f_{i,j,k} 表示考虑到第 i 到第 n 个数，当前的 mex 是 j，j 上面有 k 个不为空的地方的方案数。

考虑从 i+1 转移到 i。

• 当前的 mex 是继承的第 i+1 的 mex。

此时，当前这一位的值可以任选。分为两种情况：

1. 当前这一位是序列中第一次出现的值，也就是要让一个不为空的地方变成空，共有 k+1 个地方可以选。

2. 当前这一位不是序列中第一次出现的值，也就是不改变不为空的地方的个数，此时所有不为空的地方都能选，方案数为 j+k。

即 f_{i,j,k}=(j+1)f_{i+1,j+1,k}+(j+k)f_{i+1,j,k}。

• 当前的 mex 是从下面挖空得到的。

枚举上一个的 mex 是多少，即 f_{i,j,k}=\sum\limits_{l=k+1}^nf_{i,j+k-l+1,l}。

前缀和优化即可。