自动搬运

查看原文

来自洛谷，原作者为

	qbf！ Never Give Up

搬运于2025-08-24 23:04:17，当前版本为作者最后更新于2025-03-31 17:47:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

下文的 $\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$ 的方案数，转移如下：

• 设 $k$ 为满足 $\forall i\in[0,2^k-1],i\in A$ 的最大的 $k$，若 $k\le w-2$，则 $[2^{w-1},2^w-1]$ 中的数必定不会影响 mex-limit，我们从 $f_{w-1,c,j}$ 转移过来，系数是 $\dbinom{2^{w-1}}{i-j}$。

• 若 $k=w-1$：

  • 若 $2^{w-1}\in A$，则根据性质二，我们从 $f_{w-1,c,i-2^{w-1}}$ 转移过来。

  • 若 $2^{w-1}\notin A,(2^w-1)\in A$，则根据前面的性质，此时我们发现若 $[2^{w-1}+2^{w-2},2^w-1]$ 填满了，那么 mex-limit 还会递归到 $[2^{w-1},2^{w-1}+2^{w-2}-1]$，因此我们需要设一个辅助 DP。

    设 $g_{w,c,i}$ 表示在 $[0,2^w-1]$ 中选择 $i$ 个不同的数，且 $0$ 必须选择，$2^w-1$ 必须不选择，得到集合的 mex-limit 为 $2^c$ 的方案数，则 $f_{w,c,i}$ 会从 $g_{w-1,c,j}$ 转移过来。

  • 若 $2^{w-1}\notin A,(2^w-1)\notin A$，则根据性质四，此时 mex-limit 为 $2^{w-1}$，方案数为 $\dbinom{2^{w-1}-2}{i-2^{w-1}}$。

• 若 $k=w$，那么是平凡的。

$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)$ 的。