P11107 题解

下文的 $\lceil$操作$\rfloor$ 表示将集合 $A$ 变成 $\mathrm{Ultra(A)}$。

先考虑如何求出 $A$ 的 mex-limit，我们观察一些性质。

性质一：若存在 $i\in[0,2^k-1]$ 使得 $i\notin A$，则无论经过多少次操作，都有 $\mathrm{mex}(A)<2^k$。

于是我们可以将 $A$ 中 $\ge 2^k$ 的数删去，不影响 mex-limit。

性质二：设 $k$ 为满足 $\forall i\in[0,2^k-1],i\in A$ 的最大的 $k$，若 $2^k\in A$，则我们令 $A\leftarrow\{i-2^k\mid 2^k\le i\land i\in A\}$，不影响 mex-limit。

证明：我们发现一次操作后，$A$ 中所有数的二进制下第 $k$ 位都发生了变化，且此时 $[0,2^k-1]$ 没有被填满，因此我们可以删掉操作后 $[2^k,2^{k+1}-1]$ 的部分，即操作前 $[0,2^k-1]$ 的部分。

性质三：设 $k$ 为满足 $\forall i\in[0,2^k-1],i\in A$ 的最大的 $k$，若 $2^k\notin A$ 且 $(2^{k+1}-1)\in A$，则我们可以令 $A\leftarrow\{i\oplus(2^{k+1}-1)\mid 2^k\le i\land i\in A\}$，不影响 mex-limit。

证明：此时 $\mathrm{mex(A)}-1=2^k-1$，故操作一次后 $2^{k+1}-1$ 就变成了 $2^k$，再利用性质二即可得证。

性质四：设 $k$ 为满足 $\forall i\in[0,2^k-1],i\in A$ 的最大的 $k$，若 $2^k\notin A$ 且 $(2^{k+1}-1)\notin A$，则 $A$ 的 mex-limit 为 $2^k$。

性质五：任意集合都是 mex-stable 的，且 mex-limit 必定为 $2$ 的幂。

有了这几个性质，我们就可以进行 DP 了，设 $f_{w,c,i}$ 表示我们在 $[0,2^w-1]$ 中选择 $i$ 个不同的数，且 $0$ 必须选择，得到集合的 mex-limit 为 $2^c$ 的方案数，转移如下：

$g$ 的转移和 $f$ 是类似的，注意 $f$ 和 $g$ 在转移时可能有一些边界情况。

若直接实现这个 DP，则时间复杂度是 $\mathcal O(2^{2k}\mathrm{poly}(k))$ 级别的，注意到转移是卷积的形式，且模数 $M$ 减去一后可以被 $2^{18}$ 整除，故我们只需先求出 $M$ 的原根，就可以用 NTT 优化转移的时间复杂度。

最后的时间复杂度是 $\mathcal O(\sum_{i=0}^k2^ii^2)=\mathcal O(2^kk^2)$ 的。