# 镜像行对容斥

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

## 先处理对角线

设 $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 位整数中进行并及时取模，减法归一到非负余数。零指数因子先返回一，实际需要访问的自由格数一定非负。