11.4 联测

A

区间 mex 在随机数据下期望是 $\log n$ 级别的。

直接暴力做，复杂度 $O(n\log^2n)$。

B

对于一个 $k$，只需要找到 $n$ 使得 $k\in((n-1)^3,n^3]$ 的构造方法。

发现 $k \ge n^2$ 是一定能使三个面都是满的，所以只需要考虑 $k\in((n-1)^3,n^2)$。

发现这个区间在 $n>3$ 是空集。于是 $n\le3$ 打表，$n>3$ 直接把三个面塞满，剩下乱放。

C

把删除看成黑白染色。把边分成三类：

1. 两端都是黑色。
2. 两端都是白色。
3. 两端一黑一白。

不难想到容斥，即钦定某一类边可以出现。

• 都不能出现。如果 $m=0$，答案为 $2^n$。否则，答案为 $0$。

• 1 类边可以出现。答案为 $2^{c1}$，$c1$ 为孤立点的个数。

• 2 类边可以出现。同上。

• 3 类边可以出现。如果原图是二分图，答案为 $2^{c2}$，$c2$ 为连通块个数。否则，答案为 $0$。

• 1,2 类边可以出现。答案为 $2^{c2}$。

• 1,3 类边可以出现，答案为图的独立集个数。

• 2,3 类边可以出现。同上。

• 1,2,3 类边可以出现。答案为 $2^n$。

现在需要解决一般图独立集计数。称编号为 $[1,\lfloor \frac{n}{2} \rfloor]$ 为左部点，反之为右部点。

考虑折半搜索。复杂度 $O(2^{\frac{n}{2}}n)$，能拿 40pts。

考虑直接 dp，令 $f_{S}$ 表示点集为 $S$ 是的独立集个数。

转移分讨，设 $x$ 为 $S$ 中编号最小的点。

• 不选 $x$，$f_S \larr f_{S-x}$。
• 选 $x$，此时不能选 $x$ 的邻域，$f_S \larr f_{S-x-to_x}$。

记忆化搜索，复杂度好像是 $O(2^{\frac{n}{2}})$，怎么证我也不知道。