P2051 [AHOI2009] 中国象棋 分析

__ryp__ · 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)

然后转移。