题解

思路推导

把未勾选单元格看作集合。为了让每一行和每一列都不完整，至少要留下 $n$ 个未勾选单元格；恰好留下 $n$ 个时，它们必须在每行、每列各出现一次，因此对应一个排列。

当 $n\ge3$ 时，存在同时与主对角线和副对角线相交的排列，所以最大勾选数为 $n^2-n$。合法的最优失败方案对应至少包含一个主对角线位置、且至少包含一个副对角线位置的排列。$n=2$ 时需要单独检查，答案为 4。

设 $D_n$ 为错排数。由容斥，所求排列数等于

其中 $C_n$ 表示同时避开两条对角线所有位置的排列数。

做法

把两条对角线位置视为棋盘上的禁用格。它们对应的二分图在 $n$ 为偶数时由 $n/2$ 个 $K_{2,2}$ 组成；$n$ 为奇数时还多一个独立禁用格。一个 $K_{2,2}$ 的 rook 多项式为 $1+4x+2x^2$，独立禁用格的多项式为 $1+x$。

若 rook 多项式中 $x^j$ 的系数为 $r_j$，则容斥得到

在中等范围内，可以逐个乘入 $1+4x+2x^2$，用二次动态规划求全部系数。

满分做法利用 $P(x)=(1+4x+2x^2)^m$ 的导数关系，令其系数为 $r_j$，可在线性时间递推相邻系数。若 $n$ 为奇数，再把系数与前一项相加，等价于乘入 $1+x$。预处理阶乘、逆元和错排数后即可回答每组测试。

正确性证明

留下的未勾选格必须命中所有行和列，因此至少有 $n$ 个；等号成立时每行每列恰有一个，正好对应一个排列。还要命中两条对角线，故该排列必须在两条对角线上都至少选中一个位置。对“完全避开主对角线”和“完全避开副对角线”做容斥，就得到 $n!-2D_n+C_n$。

rook 多项式系数 $r_j$ 等于从两条对角线的并集中选择 $j$ 个互不同行、列的禁用格的方案数。固定这些格后，剩余排列数为 $(n-j)!$。再次按选择数量做容斥，所得恰为避开全部禁用格的排列数 $C_n$。因此公式统计的正是所有最优失败方案。

复杂度分析

预处理复杂度为 $O(N)$。每组测试的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$，其中 $N$ 是输入中的最大 $n$。