本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-05 12:47:02

我们注意到一个重要的性质：每一行每一列最多只能放两个炮。

我们可以设 $f(i, j, k)$ 表示已经放完前 $i$ 行，$j$ 列是空的，$k$ 列放了一个，那么有 $m - j - k$ 列放了两个。我们并不需要知道具体是哪一列放了一个两个或者零个，只需要统计方案。

转移（这里滥用 $\gets$ 表示在原来的值上加）：

• 不动，转移到下一行：$f(i, j, k) = f(i-1, j, k)$

• 放一个，分成放到一个原来空着的列：$f(i, j, k) \gets (j+1)\cdot f(i - 1, j + 1, k - 1)$

• 放到一个原来有一个的列：$f(i, j, k) \gets (k + 1)\cdot f(i - 1, j, k + 1)$。

• 放两个，又分成两个都放到原来空着的：$f(i, j, k) \gets \dfrac12 (j + 2)(j+1)\cdot f(i - 1, j + 2, k - 2)$

• 一个放到空着的，另一个放到原来有一个的：$f(i, j, k) \gets (k + 1)(j + 1)\cdot f(i - 1, j + 1, k + 1)$

• 都原来有一个的：$f(i, j, k) \gets \dfrac12\times (k+2)(k + 1) \cdot f(i - 1, j, k + 2)$

然后转移。