# 子格计数: 补充解法

## 子集动态规划

本方案与 [alternative.cpp](alternative.cpp) 由 Codex（GPT-6）补充。出题人的空间更省的搜索见[主题解](solution.zh.md)。

用位掩码 $M$ 表示集合。定义 $Need[M]$ 为集合自身及其中所有元素对的交并结果的并集，仍用位掩码存储。取 $M$ 的最低置位所对应的元素 $p$ ，令 $R=M\setminus\{p\}$ ，则

$$Need[M]=Need[R]\cup\{p\}\cup\bigcup_{j\in R}\{p\lor j,p\land j\}$$

从 $Need[0]=0$ 开始，按掩码递增顺序计算。移除一个置位后掩码严格变小，所以依赖总已算好。若 `Need[Mask]` 的所有置位都在 `Mask` 中，就计数这个非空集合。

集合中的元素对分为完全位于 $R$ 内的一类，以及包含 $p$ 的一类；前者由 $Need[R]$ 提供，后者由循环加入，$p$ 与自身的结果就是 $p$ .因此递推准确覆盖全部必要结果。集合闭合当且仅当这些结果都属于集合，证明判定和计数正确。

这里保存的是一次二元运算所需的结果，并非反复扩张后的闭包。子集 $R$ 即使不闭合，也必须照常计算它的 $Need$ ，因为添加 $p$ 后可能恰好补齐缺失元素。

每个掩码扫描至多 $n$ 个元素，总时间 $O(n2^n)$ .`Need` 的 32 位数组及定位单个置位的 8 位查找数组共约 $5\cdot2^n$ 字节；加运算表，总空间 $O(2^n+n^2)$ .在最大规模，两数组共约 $20$ MiB。参考环境中的最慢中位数约 $0.085$ 秒，标准搜索约 $0.444$ 秒；这是增加空间换得的实测常数收益，原搜索仍具有空间优势。