子格计数: 补充解法¶

子集动态规划¶

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

用位掩码 \(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\) 秒；这是增加空间换得的实测常数收益，原搜索仍具有空间优势。