高阶扩展：补集子掩码构成的隐式图

本节目标

把“按位 AND 为零”的稠密图邻接关系改写成补集的全部子掩码，并用共享的子掩码状态层把潜在 $O(m2^n)$ 枚举压到 $O(n2^n)$。

前置知识与课前自测

前置：位掩码、子掩码、连通分量 DFS/BFS。

$x&y=0$ 等价于 $y$ 是哪个掩码的子掩码？
为每个 $x$ 枚举其全部邻点，最坏会重复访问一个掩码多少次？
若一个辅助状态已在某连通分量访问过，另一分量还可能通过它发现新点吗？

答案

1. `FULL xor x` 的子掩码。 2. 指数次。 3. 不可能；能由同一辅助状态到达的所有真实点已经与该分量连通。

问题动机

原图的邻接判定是 $O(1)$，却可能有平方级边；本节关注的不是加速一次 AND，而是怎样让许多真实点共享一次“枚举某个下闭包”的工作。

精选例题：AND Graph

来源、题意与动机

VJudge：CodeForces-986C
原题：Codeforces 986C
难度：2500；考点：补集、子掩码 DAG、隐式连通分量

给出 $m$ 个互异的 $n$ 位数，$0\le n\le22$、$m\le2^n$。若 $x&y=0$ 就连无向边，求连通分量数。

显式图可能有 $\Theta(m^2)$ 条边；即使对每个点枚举补集子掩码，总工作也可能接近 $3^n$。

Hint 1

从真实点 $x$ 跳到辅助状态 `FULL xor x`。

Hint 2

辅助状态 $s$ 可向 `s without one set bit` 走；这样恰遍历 $s$ 的全部子掩码。

Hint 3

当辅助状态 $s$ 本身是输入值时，再跳回真实点 $s$，继续展开它的补集。

Hint 4

真实点与辅助掩码用两套访问标记；每个辅助掩码全局只展开一次。

Observations 与 Editorial

建立两个逻辑层：

real(x)：只对输入集合中的数存在，代表原图顶点；
mask(s)：对所有 $0..2^n-1$ 存在，可向删掉任意一个 1 后的状态走。

从 real(x) 进入 mask(FULL xor x)。沿删位边能且只能到达它的全部子掩码 $y$，这些正是满足 $x&y=0$ 的候选；若 $y$ 在输入集合，就进入 real(y)。所以一次交替的 real -> mask downset -> real 精确模拟原图的一条边，反复交替精确模拟原图路径。

从每个尚未访问的真实点启动一次搜索并计数。辅助层虽然使用有向删位边，但只承担“批量枚举下闭包”；原图的对称性由每个真实点都能再次进入自己补集保证。

正确性证明

合法性： 从 real(x) 到达的任何真实点 $y$ 都是 FULL xor x 的子掩码，因此 $x&y=0$，对应原图边；拼接得到的搜索路径都是原图路径。
完备性： 对任意原图边 $x-y$，$y\subseteq FULL\oplus x$，删位链必能从该补集到 $y$，所以搜索不会漏掉相邻点，归纳后不漏同分量点。
全局剪枝： 若 mask(s) 已从某分量展开，它可到达的全部真实点都已并入该分量。后来再次到达 $s$ 就已经证明两个入口连通，无需重扫其下闭包。

每个真实点访问一次；每个辅助掩码访问一次并枚举至多 $n$ 个删位转移。时间 $O(n2^n+m)$，空间 $O(2^n)$，适合 $n\le22$。

实现指南、核心伪代码与附件

explore(real x):
    if real x visited: return
    mark real x
    explore_mask(FULL xor x)

explore_mask(s):
    if mask s visited: return
    mark mask s
    if s is an input value: explore(real s)
    for each set bit b of s:
        explore_mask(s xor b)

for each input value x not visited:
    components += 1
    explore(real x)

完整 GNU C++17 实现

扩展与联系

辅助子掩码层本质是布尔格上的有向无环图；SOS DP 也在同一格上聚合信息，但这里做的是可达性与连通分量，而不是数值求和。

实现、失效边界

两层必须分开标记：辅助掩码可能不是原图顶点。
递归深度虽然单次删位不超过 22，但真实层交替可很长；附件用显式栈避免调用栈风险。
若邻接条件改成 popcount(x&y)<=1，一个补集下闭包不再精确描述邻居，需要增加缺失位状态或换模型。
解释为什么复杂度是 $n2^n$ 而不是 $3^n$；再画出 $n=3$、输入 {1,2,6} 的两层搜索。

总结与自检

为什么需要真实层与掩码层两套标记？全局跳过已访问辅助状态为什么不会把两个分量错误合并？

课后训练建议

先写显式 $O(m^2)$ 暴力作为随机对拍，再实现两层图。卡 20 分钟后看 Hint 2，先不要看完整伪代码。

02-高阶扩展-补集子掩码隐式图.md 4.8 KB Historia Czysty