[AHOI2009]中国象棋 题解
题目地址:洛谷:【P2051】[AHOI2009]中国象棋 – 洛谷、BZOJ:Problem 1801. — [Ahoi2009]chess 中国象棋
题目描述
这次小可可想解决的难题和中国象棋有关,在一个N行M列的棋盘上,让你放若干个炮(可以是0个),使得没有一个炮可以攻击到另一个炮,请问有多少种放置方法。大家肯定很清楚,在中国象棋中炮的行走方式是:一个炮攻击到另一个炮,当且仅当它们在同一行或同一列中,且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧!
输入输出格式
输入格式:
一行包含两个整数N,M,之间由一个空格隔开。
输出格式:
总共的方案数,由于该值可能很大,只需给出方案数模9999973的结果。
输入输出样例
输入样例#1:
1 3
输出样例#1:
7
说明
样例说明
除了3个格子里都塞满了炮以外,其它方案都是可行的,所以一共有222-1=7种方案。
数据范围
100%的数据中N和M均不超过100
50%的数据中N和M至少有一个数不超过8
30%的数据中N和M均不超过6
题解
这道题在状态设计出来以后就没什么了。显然每行每列的炮不能超过2个,用dp[i][j][k]表示正在排第i行,有j列有1个炮,有k列有2个炮的状态。下面是若干转移方程。
①这一次不填炮
dp[i][j][k] += dp[i-1][j][k]
②这一次填1个炮,填在没炮的列,乘法原理选择一列
dp[i][j+1][k] += dp[i-1][j][k] * (m - j - k)
③这一次填1个炮,填在本来有1个炮的列,乘法原理选择一列
dp[i][j-1][k+1] += dp[i-1][j][k] * j
④这一次填2个炮,都填在没有填过的列,组合选择2列
dp[i][j+2][k] += dp[i-1][j][k] * C_{m-j-k}^2
⑤这一次填2个炮,分别填在没填过和有1个炮的列,乘法原理分别选择
dp[i][j][k+1] += dp[i-1][j][k] * (m - j - k) * j
⑥这一次填2个炮,都填在有1个炮的列,组合选择2列
dp[i][j+2][k] += dp[i-1][j][k] * C_j^2
这些写全了再对填完n列的各种情况加和即可。最后滚动数组优化下空间。
代码
注:这个式子比较长建议复制出去看或者看上面的式子。
// Code by KSkun, 2018/2
#include <cstdio>
#include <cstring>
typedef long long LL;
const int MO = 9999973;
int n, m;
LL dp[2][105][105], ans = 0;
inline LL cal(LL x) {
return x * (x - 1) / 2;
}
inline int g(int x) {
return x & 1;
}
int main() {
scanf("%d%d", &n, &m);
dp[0][0][0] = 1;
for(int i = 1; i <= n; i++) { // i行
for(int j = 0; j <= m; j++) { // 枚举1棋列
for(int k = 0; j + k <= m; k++) { // 枚举2棋列
if(dp[g(i - 1)][j][k]) {
//noif
dp[g(i)][j][k] = (dp[g(i)][j][k] + dp[g(i - 1)][j][k]) % MO; // 不放
if(m - j - k > 0)
dp[g(i)][j + 1][k] = (dp[g(i)][j + 1][k] + dp[g(i - 1)][j][k] * (m - j - k)) % MO; // 放1 0棋
if(j > 0)
dp[g(i)][j - 1][k + 1] = (dp[g(i)][j - 1][k + 1] + dp[g(i - 1)][j][k] * j) % MO; // 放1 1棋
if(m - j - k > 1)
dp[g(i)][j + 2][k] = (dp[g(i)][j + 2][k] + dp[g(i - 1)][j][k] * cal(m - j - k)) % MO; // 放2 0|0
if(m - j - k > 0 && j > 0)
dp[g(i)][j][k + 1] = (dp[g(i)][j][k + 1] + dp[g(i - 1)][j][k] * (m - j - k) * j) % MO; // 放2 1|0
if(j > 1)
dp[g(i)][j - 2][k + 2] = (dp[g(i)][j - 2][k + 2] + dp[g(i - 1)][j][k] * cal(j)) % MO; // 放2 1|1
}
}
}
memset(dp[g(i + 1)], 0, sizeof dp[g(i + 1)]);
}
for(int i = 0; i <= m; i++) {
for(int j = 0; i + j <= m; j++) {
ans = (ans + dp[g(n)][i][j]) % MO;
}
}
printf("%lld", ans);
return 0;
}