Luogu P2051 [AHOI2009] 中国象棋

DP

把题面翻译成人话:n*n的棋盘,每行每列最多放两枚棋子,求方案数. 可以用$f[i][j][k]$来描述在前i行j列有1个棋子,k列有2个棋子. 接下来对放棋进行分类讨论.

Ⅰ.不放棋.直接继承上一次的方案数.

显然可得:$f[i][j][k]+=f[i-1][j][k]$.

Ⅱ.放一枚棋.

①.放在有一枚棋子的一列.

放置棋子后会使j减少1,k增加1,这种方案共有$ j-1$种,因此可以得到: $f[i][j][k]+=f[i-1][j+1][k-1]\times (j+1)$.

②.放在没有棋子的一列.

放置棋子后会使j增加1,k不变,这种方案共有$(m-(j-1)-k)$种.因此可以得到: $f[i][j][k] += f[i - 1][j - 1][k] \times (m - j - k + 1)$.

Ⅲ.放两枚棋.

①.都放在有一枚棋子的两列.

放置棋子后会使j减少2,k增加2. 而显然,这种方案数为$C^2_{j+2}$.化简该式,$C^2_{j+2}=\frac{(j+2)!}{2!\times j!}=\frac{j!\times (j+1)\times (j +2)}{2!\times j!}=\frac{(j+1)(j+2)}{2}$. 可得:$ f[i][j][k] += f[i - 1][j + 2][k - 2] \times (j + 2) \times (j + 1) / 2$

②.都放在没有棋子的两列.

放置后会使j增加2,k不变.而这种方案数也是很显然的,为$C^2_{m-(j-2)-k}$. 化简该式:$C^2_{m-(j-2)-k}=\frac{(m-j-k+2)!}{2!\times (m-j-k)!}=\frac{(m-j-k)!\times (m-j-k+1)\times (m-j-k+2)}{2!\times(m-j-k)!}=\frac{(m-j-k+1)\times (m-j-k+2)}{2}$. 可得:$ f[i][j][k] += f[i - 1][j - 2][k] \times (m - j - k + 1) \times (m - j - k + 2) / 2$

③.分别放在有一枚棋子和没有棋子两列.

放置棋子在有棋子列后会使j减少1,k增加1,放置棋子在无棋子列后会使j增加1,k不变.最终其实j没有改变,只是k增加了1. 根据乘法原理,方案数显然,为$[m-j-(k-1)]\times j$种. 可得:$ f[i][j][k] += f[i - 1][j][k - 1] \times (m - j - k + 1) \times j $. 最后统计答案,这道题就结束了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
#define N 105
#define MO 9999973
#define ll long long

namespace Gekoo {
int n, m;
ll f[N][N][N], ans;//f[行][有几列放了1个棋子][有几列放了两个棋子]

void QAQ() {
scanf("%d%d", &n, &m);
f[0][0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= m - j; k++) {
//下棋时分三种情况.
//1.放0个棋子
(f[i][j][k] += f[i - 1][j][k]) %= MO;//直接加上之前的
//2.放1个棋子
if (k >= 1) (f[i][j][k] += f[i - 1][j + 1][k - 1] * (j + 1)) %= MO;//(1)放在有棋子的一列
if (j >= 1) (f[i][j][k] += f[i - 1][j - 1][k] * (m - j - k + 1)) %= MO;//(2)放在没棋子的一列
//3.2个棋子
if (j >= 2) (f[i][j][k] += f[i - 1][j - 2][k] * (m - j - k + 1) * (m - j - k + 2) / 2) %= MO;//(1)0 and 0
if (k >= 1) (f[i][j][k] += f[i - 1][j][k - 1] * (m - j - k + 1) * j) %= MO;//(2)0 and 1
if (k >= 2) (f[i][j][k] += f[i - 1][j + 2][k - 2] * (j + 2) * (j + 1) / 2) %= MO;//(3)1 and 1
}
}
}
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= m; k++) {
(ans += f[n][j][k]) %= MO;
}
}
printf("%lld\n", (ans + MO) % MO);
}
}

using namespace Gekoo;

signed main() {
QAQ();
return 0;
}
# DP

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×