这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧！
由于比较弱的缘故,稍微涉及数学的题目就做了很久..
设计状态$dp(k,n_{1},n_{2})$为考虑前k行时,设有$n_1$列放一个炮,$n_2$列放两个炮(剩下的列不放炮)时的所有方案数
若在第$k$行放置$0$个炮
$dp(k,n_1,n_2) += dp(k-1,n_1,n_2)$
若在第$k$行放置$1$个炮
- 放在只有$0$个炮的列上:$dp(k,n_1,n_2) += dp(k - 1,n_1 - 1,n_2)\times (第k-1行的n_0)$
- 放在只有$1$个炮的列上:$dp(k,n_1,n_2) += dp(k - 1,n_1 + 1,n_2 - 1)\times (第k-1行的n_1)$
若在第$k$行放置$2$个炮
- 两个炮放在只有$0$个炮的列上
- 两个炮放在只有$1$个炮的列上
- 一个炮放在有$0$个炮的列上,一个炮放在有$1$个炮的列上
具体转移与约束见下代码
注意到复杂度为$O(nm^2)$
所以当$m>n$时交换一下两者可能会快一些??
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#define llint long long
using namespace std;
const llint base = 9999973;
llint dp[150][150][150];
int main (){
int n,m;
cin >> n >> m;
dp[0][0][0] = 1;
for (int i = 1;i <= n;++ i){
for (int n1 = 0;n1 <= m;++ n1){
for (int n2 = 0;n2 <= m - n1;++ n2){
//put 0 pao
dp[i][n1][n2] = dp[i - 1][n1][n2];
//put 1 pao
if(n1 > 0)
dp[i][n1][n2] = (dp[i - 1][n1 - 1][n2] * (m - n1 + 1 -n2) % base + dp[i][n1][n2]) % base;
if(n2 > 0)
dp[i][n1][n2] = (dp[i - 1][n1 + 1][n2 - 1] * (n1 + 1) % base + dp[i][n1][n2]) % base;
//put 2 pao
if(n1 > 1){
int n0_ = m - n1 + 2 - n2;
dp[i][n1][n2] = ((dp[i - 1][n1 - 2][n2] * (n0_ * n0_ - n0_) / 2) % base + dp[i][n1][n2]) % base;
}
if(n2 > 1){
int n1_ = n1 + 2;
dp[i][n1][n2] = ((dp[i - 1][n1_][n2 - 2] * (n1_ * n1_ - n1_) / 2) % base + dp[i][n1][n2]) % base;
}
if(n2 > 0 && n1 > 0){
int n0_ = m - n1 + 1 - n2;
dp[i][n1][n2] = (dp[i - 1][n1][n2 - 1] * (n1 * n0_) % base + dp[i][n1][n2]) % base;
}
}
}
}
llint ans = 0;
for (int i = 0;i <= m;++ i)
for (int j = 0;j <= m - i;++ j)
ans = (ans + dp[n][i][j]) % base;
cout << ans;
return 0;
}