题目描述
这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧！
输入输出格式
输入格式：一行包含两个整数N，M，之间由一个空格隔开。
输出格式：总共的方案数，由于该值可能很大，只需给出方案数模9999973的结果。
输入输出样例
1 3
7
说明
样例说明
除了3个格子里都塞满了炮以外，其它方案都是可行的，所以一共有2*2*2-1=7种方案。
数据范围
100%的数据中N和M均不超过100
50%的数据中N和M至少有一个数不超过8
30%的数据中N和M均不超过6
留给读者一点思考时间吧！
接下来，我来讲讲我怎么想的吧！
首先，做题之前，我们要冷静，不要看到省选题就 想AC 怕！
留心观察数巨范围，我们发现，这大概是标准的2-3维的动态规划题的数据规模。
既然这么想，那么我们肯定先考虑高维的状态设计了。
我是这么设计的：
首先它有n行m列，而两个炮又不能在一列，所以这么定义$f[i][j][k]$.
i表示已经放了i行棋子，作为第一维来枚举。
j表示在m列里，有j列只有一个炮。
最后，k表示有k列有两个炮。那么状态设计好了，怎么转移呢？
肯定的，我们先来枚举i行。
在这i行里，我们下棋的方案数：
1.首先肯定先要继承上一行枚举完的所有方案数，所以$$f[i][j][k]=f[i-1][j][k]$$
2.从最简单的下起，我们先一行只下一个吧，那么先找到空的行，没有棋子，我们可以随便怎么下。
那么有：$$f[i][j][k]+=f[i-1][j-1][k]*(m-j-k+1)$$
3.还有，我们还可以把这一个炮下在只有一个炮的那一列，那么：$$f[i][j][k]+=f[i-1][j+1][k-1]*(j+1)$$
4.同时，枚举新的一行时，我们可以在这一行下两个棋子。
还是从最简单的开始，我们下在没有炮的那两列：$$f[i][j][k]+=f[i-1][j-2][k]*C(m-j-k+2,2)$$
5.我们还可以下在两个原来都有一个炮的那两列：$$f[i][j][k]+=f[i-1][j+2][k-2]*C(j+2)$$
6.最后，其实还有一种下法，我们可以将一个炮下在没有炮的那一列，另一个下在有炮的一列。
那么有：$$f[i][j][k]+=f[i-1][j][k-1]*j*(m-j-k+1)$$
P.S. 为了不让数组越界，我们要加一些判断，如$if (j>=1)$之类的。
代码在下面啦
#include <bits/stdc++.h> #define C(x) ((x)*(x-1)/2) using namespace std; int main() { int n,m,ans=0,mo=9999973; long long f[105][105][105]={1}; cin>>n>>m; for (int i=1;i<=n;i++) for (int j=0;j<=m;j++) for (int k=0;k+j<=m;k++) { f[i][j][k]=f[i-1][j][k]; if (j>=1) f[i][j][k]+=f[i-1][j-1][k]*(m-k-j+1),f[i][j][k]%=mo; if (k>=1) f[i][j][k]+=f[i-1][j+1][k-1]*(j+1),f[i][j][k]%=mo; if (j>=2) f[i][j][k]+=f[i-1][j-2][k]*C(m-j-k+2),f[i][j][k]%=mo; if (k>=1) f[i][j][k]+=f[i-1][j][k-1]*j*(m-k-j+1),f[i][j][k]%=mo; if (k>=2) f[i][j][k]+=f[i-1][j+2][k-2]*C(j+2),f[i][j][k]%=mo; } for (int j=0;j<=m;j++) for (int k=0;k+j<=m;k++) ans+=f[n][j][k],ans%=mo; cout<<ans<<endl; return 0; }