P11107 题解

qbf！ · 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，那么是平凡的。