洛谷 P2051 [AHOI2009]中国象棋

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

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

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

放两个一个０一个1为例
方程为 $f[i+1][j][k+1] = (f[i+1][j][k+1] +f[i][j][k] * r * j)$
这里用刷表法，比填表法方便非常多，但是要注意有些状态是不存在的（比如 $k$ 与 $j$ 都等于 $m$ ）
所以一开始要判断之前有没有刷到过这个状态

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

最后就是把最后一行的所有情况加起来就是答案
注意可以用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
", ans);
	
	return 0;
}