Luogu P2051 [AHOI2009]中国象棋(DP)
文章目录
题目描述
给定一个 $n \times m$ 的棋盘,求放棋子使得每一行每一列棋子个数小于等于 $2$ 的方案总数
$1 \le n,m \le 100$
简要做法
状态比较关键,设 $f(i,j,k))$ 表示前 $i$ 行,有 $j$ 列存在一个棋子,有 $k$ 列存在二个棋子的方案数
当这一行不放棋子,方案为 $f(i-1,j,k)$
放在空列,放一个,方案为 $f(i-1,j-1,k) \times (m - (j - 1) - k)$
放在空列,放两个,方案为 $f(i-1,j-2,k) \times C_{m-(j-2)-k}^2$
放在已有一个的列,放一个,方案为 $f(i-1,j+1,k-1) \times (j+1)$
放在已有一个的列,放两个,方案为 $f(i-1,j+2,k-2)\times C_{j+2}^2$
在空列和已有一个的列各放一个,方案为 $f(i-1,j,k-1) \times j \times (m-j-(k-1))$
参考代码
#include <stdio.h>
#include <algorithm>
#define int long long
const int N = 2e2 + 5;
const int magic = 4999987;
const int P = 9999973;
int n, m, ans;
int fac[N], inv[N];
int f[N][N][N];
int read()
{
int x = 0, f = 1;
char ch = getchar();
while ('0' > ch or ch > '9')
f = ch == '-' ? -1 : 1, ch = getchar();
while ('0' <= ch and ch <= '9')
x = x * 10 + ch - 48, ch = getchar();
return x * f;
}
int C(int n) { return n * (n - 1) % P * magic % P; }
signed main()
{
n = read(), m = read(), f[0][0][0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++)
for (int k = 0; k + j <= m; f[i][j][k++] %= P)
{
f[i][j][k] = f[i - 1][j][k];
if (k >= 1)
f[i][j][k] += f[i - 1][j + 1][k - 1] * (j + 1) % P,
f[i][j][k] += f[i - 1][j][k - 1] * j * (m - j - k + 1) % P;
if (k >= 2)
f[i][j][k] += f[i - 1][j + 2][k - 2] * C(j + 2) % P;
if (j >= 1)
f[i][j][k] += f[i - 1][j - 1][k] * (m - j - k + 1) % P;
if (j >= 2)
f[i][j][k] += f[i - 1][j - 2][k] * C(m - j - k + 2) % P;
}
for (int i = 0; i <= m; i++)
for (int j = 0; j <= m; j++)
(ans += f[n][i][j]) %= P;
return printf("%lld", (ans + P) % P), 0;
}