# 子格计数: 题解

## 思路与贡献

标准程序保留出题人的强制选择、递归搜索和时间戳回滚算法。Codex（GPT-6）整理 C++17 实现，并补充搜索不变量及扫描中新增元素的说明。见 [std.cpp](std.cpp)。另提供[子集动态规划](solution-alternative.zh.md)和[逐子集枚举](solution-brute.zh.md)及各自程序。

任意一对已选择元素的交与并都必须被选择。按编号依次决定是否选择元素 $p$ ，同时用 `Selected` 记录已经选择、包括被强制选择的未来元素。元素编号仅决定搜索顺序，不表示偏序中的大小。

## 搜索与回滚

进入位置 $p$ 时，小于 $p$ 的编号已经最终决定，其余编号可能已被强制选择。

1. 若 $p$ 尚未被选择，先递归“不选 $p$”的分支。
2. 尝试选择 $p$ .对每个当前已选择的 $j$ ，检查矩阵中 $A_{p,j}$ 与 $A_{j,p}$ .它们给出交与并；若某个结果编号小于 $p$ 且未被选择，该分支与以前决定冲突，立即放弃。
3. 否则强制选择这些结果和 $p$ .只对新加入的元素写入时间戳 $p+1$ ，已有元素保持旧戳。
4. 递归到 $p+1$ .返回后仅清除时间戳为 $p+1$ 的元素。

处理完全部编号时计数一次。这个过程也数了空集，最终减一。答案至多 $2^{22}-1$ ，有符号 32 位整数足够。

## 正确性证明

一次强制选择来自子格封闭性的必要条件。若所需元素以前已经被排除，则没有任何合法补全，该分支可以剪去；否则任何包含当前已选元素的子格都必须包含这个结果。所以强制选择不会遗漏合法答案。

实现中，加入结果的循环可能读到本轮刚加入的元素。若新元素为 $p\lor j$ 或 $p\land j$ ，它与 $p$ 可比较。由格的吸收律和幂等律，再对它与 $p$ 做交并，结果只是它本身和 $p$ .因此扫描期间的新增项不会引入首次冲突检查未覆盖的、更早且被排除的元素。

对于最终选中的任意一对元素，在编号较大者被处理时，两者都已被选择，其两个运算结果都会被强制加入。较早的选择不会被当前分支的回滚移除，所以到叶子时集合对全部元素对封闭。只有全部编号处理结束才计数，因此每个计数的非空集合都是子格。

反过来，固定任意子格。按它的成员关系选择每个尚未强制决定的分支时，封闭性保证所有强制加入都属于该子格，也不会触发冲突。于是恰好到达一个对应叶子。不同选择集合对应不同叶子，故每个子格不重不漏。

## 复杂度与方案取舍

搜索树深度为 $n$ ，每层至多分成两个分支，节点总数 $O(2^n)$ .每个节点进行 $O(n)$ 扫描，时间 $O(n2^n)$ ；运算表占 $O(n^2)$ ，标记与递归栈占 $O(n)$ ，总空间 $O(n^2)$ .

子集动态规划同为 $O(n2^n)$ 时间，但需要 $O(2^n+n^2)$ 空间，当前测量更快，适合接受额外内存的场景。保留出题人空间更省的搜索作为标准程序。逐对枚举为 $O(n^2\cdot2^n)$ ，在已测完整数据上虽全部完成，但在 $1$ 秒时限下仅约 $1.29$ 倍余量，作为核对与理解用程序，不能据此保证其在目标环境通过全部数据。