【AHOI2009】中国象棋

Description

给定一个棋盘，在棋盘上放入m个炮，使得炮两两之间不能攻击，求出方案数。

Solution

考虑设计一个dp，定义f[i][j][k]表示前i行、有j列放了一个炮、有k列放了两个炮的方案数。

有一个显然的结论：如果方案合法，那么任何一行（列）的炮的数量最多为2。

然后我们思考转移，假设当前状态为(i, j, k)，我们有如下决策：

当前这一行可以一个炮也不放

如果一个炮都没放的列数量超过0，那么我们可以在这个位置上放一个炮

如果放一个炮的列的数量超过0，那么我们可以在这个位置上放一个炮

如果一个炮都没放的列数量超过1，那么我们可以在这个位置上放两个炮，方案数我们需要求一下组合数

如果放一个炮的列的数量超过0，且不放炮的列的数量超过0，那么我们可以在这两个位置上各放一个炮

如果放一个炮的列的数量超过1，那么我们可以在这里放两个炮，方案数我们需要求一下组合数

综上，我们讨论出了状态转移，时间复杂度为O(nm^2);

Code

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 int n, m;
 5 ll f[110][110][110];
 6 const int mod = 9999973;
 7 int calc(int x) {
 8     return x * (x - 1) / 2;
 9 }
10 int main() {
11     scanf("%d%d", &n, &m);
12     f[0][0][0] = 1;
13     for (register int i = 0; i < n; ++i) {
14         for (register int j = 0; j <= m; ++j) {
15             for (register int k = 0; k <= m; ++k) {
16                 f[i + 1][j][k] = (f[i + 1][j][k] + f[i][j][k]) % mod;
17                 if (m - j - k > 0) f[i + 1][j + 1][k] = (f[i + 1][j + 1][k] + f[i][j][k] * (m - j - k)) % mod;
18                 if (j > 0) f[i + 1][j - 1][k + 1] = (f[i + 1][j - 1][k + 1] + f[i][j][k] * j) % mod;
19                 if (j > 1) f[i + 1][j - 2][k + 2] = (f[i + 1][j - 2][k + 2] + f[i][j][k] * calc(j)) % mod;
20                 if (j > 0 && m - j - k > 0) f[i + 1][j][k + 1] = (f[i + 1][j][k + 1] + f[i][j][k] * j * (m - j - k)) % mod;
21                 if (m - j - k > 1) f[i + 1][j + 2][k] = (f[i + 2][j + 2][k] + f[i][j][k] * calc(m - j - k)) % mod;
22             }
23         }
24     }
25     ll ans = 0;
26     for (register int i = 0; i <= m; ++i)
27         for (register int j = 0; j + i <= m; ++j)
28             ans = (ans + f[n][i][j]) % mod;
29     printf("%lld
", ans % mod);
30     return 0;
31 }

AC Code