题目理解

这是一个 $N \times N$ 的棋盘，每行每列恰好有一个障碍，并且障碍不在同一行同一列（即障碍构成一个排列）。
我们要在剩下的 $N \times N - N = N(N-1)$ 个可用格子里，放置 $N$ 个棋子，使得：

1. 每行恰好一个棋子
2. 每列恰好一个棋子
3. 不能放在障碍上

等价于：在 $N \times N$ 的矩阵中，去掉 $N$ 个障碍（每行一个，每列一个），在剩下的位置中找出所有 $N \times N$ 的排列矩阵（每行每列一个棋子）。

---

转化

设障碍在第 $i$ 行的位置是 $b_i$（列下标）。
那么问题变成：在 $1 \dots N$ 的全排列中，有多少个排列 $P$ 满足 $P_i \neq b_i$ 对所有 $i$ 成立。

这就是错排问题（Derangement）：排列中每个位置 $i$ 上的数都不能是 $b_i$。
但是注意，这里的 $b_i$ 不一定是 $i$，而是任意一个 $1 \dots N$ 的排列。

---

进一步转化

因为 $b_1, b_2, \dots, b_N$ 是 $1 \dots N$ 的一个排列，我们可以通过重新标记列号，把问题变成标准的错排问题：

定义映射：设障碍位置在第 $i$ 行第 $b_i$ 列，我们想要一个排列 $P$ 使得 $P_i \neq b_i$。
我们可以把列重新编号，使得 $b_i = i$（即障碍在 $(i,i)$ 位置）。这样问题就变成：求排列 $P$ 满足 $P_i \neq i$ 的个数，这就是错排数 $D_N$。

---

错排公式

错排数递推公式：

$$D_n = (n-1)(D_{n-1} + D_{n-2}), \quad D_1 = 0, \ D_2 = 1 $$

或者通项：

$$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$$

---

结论

无论障碍的排列是什么，只要每行每列一个障碍，方案数就是 $N$ 的错排数 $D_N$。

验证样例: $N=2$，错排数 $D_2 = 1$，与样例输出一致。