镜像行对容斥¶

Codex（GPT-6）：应用容斥原理，按选中行的镜像关系合并状态，给出证明与计算程序。本方案可以通过完整数据，能独立生成答案表。

先处理对角线¶

设 \(A_d\) 是钦定 \(d\) 条指定长对角线全黑、同时每行每列均有白格的方案数，其中 \(d=0,1,2\) .两条单独的对角线情形对称，故最终答案为

\[ A_0-2A_1+A_2 \]

即使 \(n=1\) 时两条对角线重合，容斥也成立。空棋盘单独返回一。

对全黑行容斥¶

选择行集合 \(R\) ，钦定其中所有行全黑，记 \(r=|R|\) .令 \(f_j\) 为第 \(j\) 列中既未被选中行覆盖、又未被钦定对角线覆盖的格数。这一列至少含白格的填法为 \(2^{f_j}-1\) .列之间独立，因此该行集合贡献

\[ (-1)^r\prod_{j=1}^{n}(2^{f_j}-1) \]

对所有 \(R\) 求和即可得到 \(A_d\) .这是容斥原理：任何出现全黑行的棋盘被抵消，其余棋盘保留一次。

当 \(d=0\) 时，所有列的自由格数都是 \(n-r\) ，因此

\[ A_0=\sum_{r=0}^{n}(-1)^r\binom nr(2^{n-r}-1)^n \]

当 \(d=1\) 时，有 \(r\) 列的对角线格已经位于选中行，剩余 \(n-r\) 列另损失一个自由格，因此

\[ A_1=\sum_{r=0}^{n}(-1)^r\binom nr(2^{n-r}-1)^r(2^{n-r-1}-1)^{n-r} \]

任何零次幂因子直接取一，不求值其底数，避免对不存在的负自由格数取幂。

同时钦定两条对角线¶

将行编号 \(i,n+1-i\) 组成镜像对，共 \(h=\lfloor n/2\rfloor\) 对。设其中有 \(t,u,v\) 对分别选中零行、一行、两行，满足 \(t+u+v=h\) .单行选择有两个方向，所以此分类的行集合数是

\[ \binom ht\binom{h-t}{u}2^u \]

若有中心行，令 \(c\in\{0,1\}\) 表示是否选中；偶数阶只允许 \(c=0\) .选中行数 \(r=u+2v+c\) .三类镜像对分别对应 \(2t,2u,2v\) 列，其自由格数分别为 \(n-r-2,n-r-1,n-r\) .中心列只含一个不同的对角线格：中心行未选时属于第二类，选中时属于第三类。

故每个分类贡献

\[ (-1)^r\binom ht\binom{h-t}{u}2^u (2^{n-r-2}-1)^{2t} (2^{n-r-1}-1)^{2u+(n\bmod2)-c} (2^{n-r}-1)^{2v+c} \]

对全部分类求和得到 \(A_2\) .每个行集合恰好落入一个分类，且同类集合的自由格数分布相同，故合并不改变容斥之和。

复杂度与边界¶

计算一阶需要 \(O(n^2\log n)\) 时间；生成从零到 \(N\) 的全部答案需要 \(O(N^3\log N)\) 时间及 \(O(N^2)\) 空间，后者用于组合数表。所有乘法在 64 位整数中进行并及时取模，减法归一到非负余数。零指数因子先返回一，实际需要访问的自由格数一定非负。