洛谷 P2051 [AHOI2009]中国象棋

这道题主要是状态很难想到
首先可以看出每行每列不能超过2个棋子
也就是说有0， 1， 2三种状态

所以可以一行一行来处理
那就用表示前i行，有列放了一个棋子，有列放了2个棋子的方案数
放了0个棋子的列数是
那么这个时候状态转移方程就非常好写了。
对于当前这一行可以不放，放一个，放两个棋子
０表示没有棋子的列，1表示有1个棋子的列。
那么有几种情况

不放
放一个在０
放一个在1
放两个都在０
放两个一个０一个1
放两个在1

放两个一个０一个1为例
方程为
这里用刷表法，比填表法方便非常多，但是要注意有些状态是不存在的（比如与都等于）
所以一开始要判断之前有没有刷到过这个状态

现在解释一个这个方程
现在是第ｉ行，要填ｉ＋１行
放一个在０的话，就有一个０变成１
所以ｊ要加１
放一个在１的话，就有一个１变成２
所以ｊ要减１，ｋ要加１
这里０的列数不用管，因为推出ｊ和ｋ就可以知道０的列数了（ｍ－ｊ－ｋ）
所以ｊ加１又减１，所以不变，而ｋ＋１
所以是
那么放一个在０一个在１的方法显然是０的列数乘上１的列数
所以就是　

最后就是把最后一行的所有情况加起来就是答案
注意可以用define来简化代码

#include<cstdio>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
#define cal(a, b) a = (a + b) % MOD
using namespace std;const int MOD = 9999973;
const int MAXN = 112;
long long f[MAXN][MAXN][MAXN], n, m, ans;int main()
{scanf("%d%d", &n, &m);f[0][0][0] = 1;REP(i, 0, n)_for(j, 0, m)for(int k = 0; k + j <= m; k++){if(!f[i][j][k]) continue;int r = m - j - k;cal(f[i+1][j][k], f[i][j][k]);if(r >= 1) cal(f[i+1][j+1][k], f[i][j][k] * r);if(j >= 1) cal(f[i+1][j-1][k+1], f[i][j][k] * j);if(r >= 2) cal(f[i+1][j+2][k], f[i][j][k] * (r * (r - 1) / 2));if(r >= 1 && j >= 1) cal(f[i+1][j][k+1], f[i][j][k] * r * j);if(j >= 2) cal(f[i+1][j-2][k+2], f[i][j][k] * (j * (j - 1) / 2));}_for(j, 0, m)for(int k = 0; k + j <= m; k++)cal(ans, f[n][j][k]);printf("%lld\n", ans);return 0;
}