题目描述
这次小可可想解决的难题和中国象棋有关，在一个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
分析
鬼知道其实我一开始想用五维
好吧，不可行
题解链接：题解 P2051 【[AHOI2009]中国象棋】
part 1 审题
首先，整理题意：
每行每列只能放至多两粒棋子
part 2 状态
好的，一格一格来是不可行了（看我的五维就知道了）
既然状态明显以行列为单位，那状态就以行列设计
暂定，需要存的状态：行，列，棋子数
其实现在是真不知道要考虑什么具体状态，先分析
part 3 转移
说实话，格不行，那就一列一列枚举
再考虑棋子，在当前行，我们可以选择：
1. 不放棋子
2. 放一粒棋子
3. 放两粒棋子
废话
emmmm，好吧。
我们放棋子的时候，会造成什么影响？
1. 有些没棋子的列，有棋子了
2. 有些只有一个棋子的列，有两个棋子了
3. 有些有两个棋子的列……好吧不能在这一列放棋子了
嗯？有什么用？用处可大了
你想想，我们需要求的是什么？
方案数。
如果我们能求出这一行不放、放一粒棋子、放两粒棋子的方案数，这问题就圆满了
怎么求？
再看看上面的分析
当我们不放棋子的时候，方案数就等于上一行求出的总方案数
当我们放一粒棋子、放两粒棋子的时候，列的状态会改变
我们该怎么表示列的状态？然后存下方案数？
放棋子，列上的棋子数在增加，我们当然不可能存下每一列的具体状态，毕竟我们不求具体的摆放方案
列的状态与棋子数有关，却与棋子具体在哪一行无关
棋子具体在哪一行，或行上的棋子具体在哪一列，只对于方案数有贡献（然而这个可以用加法、乘法原理解决），对于接下来棋子的摆放无关联
好的，状态来了
如上，我们只存下列上的具体棋子数的列数就够了
状态：
dp[第i行][只有一个棋子的列有j列][有两个棋子的列有k列] = 方案数
你问我为啥没有空列的个数？
不就是m-j-k嘛
好吧，怎么求方案？
看看我们曾经的分析：
再考虑棋子，在当前行，我们可以选择：
1. 不放棋子
2. 放一粒棋子
3. 放两粒棋子
我们放棋子的时候，会造成什么影响？
1. 有些没棋子的列，有棋子了
2. 有些只有一个棋子的列，有两个棋子了
3. 有些有两个棋子的列……好吧不能在这一列放棋子了
好的
状态转移出来了
分三种情况讨论，不放，放一粒，放两粒，分别计算
不放的时候：
放一粒棋子：
放两粒棋子：
这里解释一下放两粒棋子的转移：
放空列：dp[i][j][k] += dp[i-1][j-2][k] * C2m-(j-2)-k
放在有一个棋子的列：dp[i][j][k] += dp[i-1][j+2][k-2] * C2j+2
一个空列，一个有棋：dp[i][j][k] += dp[i-1][j-1+1][k-1] * C1m-j-(k-1) * C1j
求组合数：emm，通过观察，1的就是本身，2的可以这么求：
好了，over
代码
1 /************************** 2 User：Mandy.H.Y 3 Language:c++ 4 Problem:luogu 2051 5 Algorithm: 6 **************************/ 7 8 #include<bits/stdc++.h> 9 #define Max(x,y) ((x) > (y) ? (x) : (y)) 10 #define Min(x,y) ((x) < (y) ? (x) : (y)) 11 12 using namespace std; 13 14 const int maxn = 105; 15 const int mod = 9999973; 16 17 int n,m; 18 long long dp[maxn][maxn][maxn]; 19 20 template<class T>inline void read(T &x){ 21 x = 0;bool flag = 0;char ch = getchar(); 22 while(!isdigit(ch)) flag |= ch == '-',ch = getchar(); 23 while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar(); 24 if(flag) x = -x; 25 } 26 27 template<class T>void putch(const T x){ 28 if(x > 9) putch(x / 10); 29 putchar(x % 10 | 48); 30 } 31 32 template<class T>void put(const T x){ 33 if(x < 0) putchar('-'),putch(-x); 34 else putch(x); 35 } 36 37 void file(){ 38 freopen("2051.in","r",stdin); 39 freopen("2051.out","w",stdout); 40 } 41 42 void readdata(){ 43 read(n);read(m); 44 } 45 46 int C(int x){ 47 return x*(x-1)/2; 48 } 49 50 void work(){ 51 52 dp[0][0][0] = 1; 53 54 for(int i = 1;i <= n; ++ i){ 55 for(int j = 0;j <= m; ++ j){ 56 for(int k = 0;k <= m - j; ++ k){ 57 58 dp[i][j][k] = dp[i - 1][j][k];//第i行不放 59 60 if(j > 0) dp[i][j][k] = (dp[i][j][k] + dp[i-1][j-1][k] * (m-j+1-k)) % mod; 61 //第i行放一个，放在空列 62 63 if(k > 0) dp[i][j][k] = (dp[i][j][k] + dp[i-1][j+1][k-1] * (j+1)) % mod; 64 //第i行放一个，放在有一个棋子的列 65 66 if(j > 1) dp[i][j][k] = (dp[i][j][k] + dp[i-1][j-2][k] * C(m-j+2-k)) % mod; 67 //第i行放两个，放在空列 68 69 if(k > 1) dp[i][j][k] = (dp[i][j][k] + dp[i-1][j+2][k-2] * C(j+2)) % mod; 70 //第i行放两个，放在有一个棋子的列 71 72 if(k > 0) dp[i][j][k] = (dp[i][j][k] + dp[i-1][j][k-1] * (m-j-k+1) % mod * j) % mod; 73 //注意是 * (m-j-k+1) * j 74 //第i行放两个，一个放在有一个棋子的列 ，一个放空列 75 76 } 77 } 78 } 79 long long ans = 0; 80 for(int i = 0;i <= m; ++ i) 81 for(int j = 0;j <= m - i; ++ j){//m - i 82 ans = (ans + dp[n][i][j]) % mod; 83 } 84 85 put(ans); 86 } 87 88 int main(){ 89 // file(); 90 readdata(); 91 work(); 92 return 0; 93 }