子格计数: 题解¶
思路与贡献¶
标准程序保留出题人的强制选择、递归搜索和时间戳回滚算法。Codex（GPT-6）整理 C++17 实现，并补充搜索不变量及扫描中新增元素的说明。见 std.cpp。另提供子集动态规划和逐子集枚举及各自程序。
任意一对已选择元素的交与并都必须被选择。按编号依次决定是否选择元素 \(p\) ，同时用 Selected 记录已经选择、包括被强制选择的未来元素。元素编号仅决定搜索顺序，不表示偏序中的大小。
搜索与回滚¶
进入位置 \(p\) 时，小于 \(p\) 的编号已经最终决定，其余编号可能已被强制选择。
- 若 \(p\) 尚未被选择，先递归“不选 \(p\)”的分支。
- 尝试选择 \(p\) .对每个当前已选择的 \(j\) ，检查矩阵中 \(A_{p,j}\) 与 \(A_{j,p}\) .它们给出交与并；若某个结果编号小于 \(p\) 且未被选择，该分支与以前决定冲突，立即放弃。
- 否则强制选择这些结果和 \(p\) .只对新加入的元素写入时间戳 \(p+1\) ，已有元素保持旧戳。
- 递归到 \(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\) 倍余量，作为核对与理解用程序，不能据此保证其在目标环境通过全部数据。