[AHOI2009]中国象棋——[计数DP]

【题目描述】

这次小可可想解决的难题和中国象棋有关&＃xff0c;在一个N行M列的棋盘上&＃xff0c;让你放若干个炮&＃xff08;可以是0个&＃xff09;&＃xff0c;使得没有一个炮可以攻击到另一个炮&＃xff0c;请问有多少种放置方法。大家肯定很清楚&＃xff0c;在中国象棋中炮的行走方式是&＃xff1a;一个炮攻击到另一个炮&＃xff0c;当且仅当它们在同一行或同一列中&＃xff0c;且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧&＃xff01;

【输入格式】

一行$n,m(n,m\le 100)$

【输出格式】

一行&＃xff0c; 表示方案数&＃xff08;对9999973取模&＃xff09;

$SampleInput$

1 3

$SampleOutput$

7

【题意分析】
感谢大佬&＃xff1a;顾z

非常像状压&＃xff0c;但是100你是压不了的&＃xff0c;考虑计数
根据规则转化题意&＃xff1a;求每行每列棋子不超过两个的方案数

$dp[i][j][k]$表示前 $i$ 行&＃xff0c;有 $j$ 列放了一个棋子&＃xff0c;有 $k$ 列放了两个棋子的方案数
那么答案就是∑i&＃61;0m∑j&＃61;0mdp[n][i][j]\sum\limits_{i&＃61;0}^m\sum\limits_{j&＃61;0}^mdp[n][i][j]i&＃61;0∑m​j&＃61;0∑m​dp[n][i][j]

显而易见当前第 $i$ 行最多放 $2$ 个棋子&＃xff0c;那么我们可以分类讨论了&＃xff1a;

• 初始情况
  $$dp[0][0][0]\&＃61;1$$
• 不放任何棋子
  继承上一行状态
  $$dp[i][j][k]\&＃43;\&＃61;dp[i-1][j][k]$$
• 放一个棋子
  放在没有棋子的一列&＃xff0c;会使 $j$ 增加1&＃xff0c;所以要寻找 $j-1$ 列的状态
  因为放在空列&＃xff0c;所以有$m-(j-1)-k$种放法
  $$dp[i][j][k]\&＃43;\&＃61;dp[i-1][j-1][k]\ast (m-(j-1)-k)$$放在有一个棋子的一列&＃xff0c;会使 $k$ 增加1&＃xff0c; $j$减少1&＃xff0c;所以要寻找$j\&＃43;1,k-1$的状态
  那么有$j\&＃43;1$种放法。
  $$dp[i][j][k]\&＃43;\&＃61;dp[i-1][j\&＃43;1][k-1]\ast (j\&＃43;1)$$
• 放两个棋子
  放在两个空列&＃xff0c;会使$j$增加2&＃xff0c;所以要寻找$j-2$的状态
  在空列中选两个&＃xff0c;即C(m−(j−2)−k)2C_{(m-(j-2)-k)}^{2}C(m−(j−2)−k)2​种放法
  $$dp[i][j][k]\&＃43;\&＃61;dp[i-1][j-2][k]\ast c(m-(j-2)-k,2)$$放在一个空列&＃xff0c;一个有一个棋子的列&＃xff0c;使$j$增加1又减少1&＃xff0c;k增加1&＃xff0c;所以要寻找$j,k-1$的状态
  根据乘法原理有$j\ast (m-j-(k-1))$种放法
  $$dp[i][j][k]\&＃43;\&＃61;dp[i-1][j][k-1]\ast j\ast (m-j-(k-1))$$放在两个有一个棋子的列&＃xff0c;使$k$增加2&＃xff0c;$j$减少2&＃xff0c;所以要寻找$j\&＃43;2,k-2$的状态
  在有一个棋子的列种选两个&＃xff0c;即Cj&＃43;22C_{j&＃43;2}^{2}Cj&＃43;22​种放法
  $$dp[i][j][k]\&＃43;\&＃61;dp[i-1][j\&＃43;2][k-2]\ast c(j\&＃43;2,2)$$

注意边界&＃xff1a;对于需要减少的参数&＃xff0c;要判断是否大于等于0
别忘了取%

Code:

#include
#include
#include
#include
#include
#include
#include
#define rep(x,y,z) for (register int x &＃61; y; x <&＃61; z; x&＃43;&＃43;)
#define MAXN 200
#define qy 9999973
using namespace std;long long dp[MAXN][MAXN][MAXN];inline long long C (int x) {return (long long) (x * (x - 1) / 2) % qy;
} int main () {int n, m; scanf ("%d %d", &n, &m), dp[0][0][0] &＃61; 1;rep (i, 1, n) rep (j, 0, m) rep (k, 0, m - j) {dp[i][j][k] &＃61; dp[i-1][j][k];if (j >&＃61; 1) dp[i][j][k] &＃43;&＃61; dp[i-1][j-1][k] * (m-(j-1)-k);if (k >&＃61; 1) dp[i][j][k] &＃43;&＃61; dp[i-1][j&＃43;1][k-1] * (j&＃43;1);if (j >&＃61; 2) dp[i][j][k] &＃43;&＃61; dp[i-1][j-2][k] * C (m-(j-2)-k);if (k >&＃61; 2) dp[i][j][k] &＃43;&＃61; dp[i-1][j&＃43;2][k-2] * C (j&＃43;2);if (k >&＃61; 1) dp[i][j][k] &＃43;&＃61; dp[i-1][j][k-1] * j * (m-j-(k-1));dp[i][j][k] %&＃61; qy;}long long ans &＃61; 0;rep (i, 0, m) rep (j, 0, m) ans &＃43;&＃61; dp[n][i][j], ans %&＃61; qy;printf ("%lld", ans);return 0;
}