# 题解：没有全黑直线的棋盘

出题人解法：预先计算固定定义域的答案，再顺序输出。Codex（GPT-6）验证答案表，并补充按镜像行对分类的容斥计算程序与证明。

## 固定答案表（首选）

题目没有输入，输出固定的 21 个余数。[标准程序](std.cpp)保存这些数并逐行输出。对最大阶数 $N$ ，在线时间和表空间均为 $O(N)$ ；此处 $N=20$ .正确性还需要说明这些常量如何得到，不能仅以存在一张表作为证明。

[容斥方案](solution-alternative.zh.md)给出完整推导，[计算程序](alternative.cpp)在运行时重新生成全部答案，与固定表完全一致。它同样通过完整数据；其价值是答案可直接重建，而固定表减少在线计算。两者都包含 $n=0$ 的特判。

## 按列覆盖状态的计算思路

出题人的另一种计算思路是逐行填色：状态集合 $S$ 表示还未出现白格的列。当前行从这些列中选择子集 $U$ 放白格，更新为 $S\setminus U$ ；已经出现白格的列可任意填色，但要排除本行全黑。若钦定某条对角线全黑，该行对应格子不能放白。

逐行枚举全部合法选择，初始 $S$ 为所有列，最后取 $S=\varnothing$ ，即可确保行列均不全黑。每个棋盘对应唯一的逐行选择，所以没有重复计数。再对两条对角线做容斥。枚举状态及其子集需要每阶 $O(n3^n)$ 时间、$O(2^n)$ 空间；它适合离线小规模计算，不能作为完整范围的在线标程。镜像行对分类在本题中避免了指数枚举。

验证包括所有 $n\le4$ 的棋盘穷举、21 个固定常量与计算程序逐项比较。见[测试说明](tests/README.md)和[性能记录](../../../docs/benchmark-R36.json)。