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

## 本节目标

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

## 前置知识与课前自测

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

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

<details><summary>答案</summary>

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

</details>

## 问题动机

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

## 精选例题：AND Graph

### 来源、题意与动机

- VJudge：[CodeForces-986C](https://vjudge.net/problem/CodeForces-986C)
- 原题：[Codeforces 986C](https://codeforces.com/problemset/problem/986/C)
- 难度：2500；考点：补集、子掩码 DAG、隐式连通分量

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

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

<details><summary>Hint 1</summary>从真实点 $x$ 跳到辅助状态 `FULL xor x`。</details>
<details><summary>Hint 2</summary>辅助状态 $s$ 可向 `s without one set bit` 走；这样恰遍历 $s$ 的全部子掩码。</details>
<details><summary>Hint 3</summary>当辅助状态 $s$ 本身是输入值时，再跳回真实点 $s$，继续展开它的补集。</details>
<details><summary>Hint 4</summary>真实点与辅助掩码用两套访问标记；每个辅助掩码全局只展开一次。</details>

## 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$。

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

```text
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 实现](../../参考实现/03-Bitset/CodeForces-986C.cpp)

## 扩展与联系

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

## 实现、失效边界

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

## 总结与自检

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

## 课后训练建议

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