P2051 [AHOI2009] 中国象棋 题解

DP好题？
首先确定，每一行/列只能放至多两个棋子，这么少，所以我们的状态肯定和棋子数有关。
由于我们不关注具体的方案数，所以我们不妨只关心对应棋子数量的行/列的数量。同时，由于考虑行和列都是一样的，所以我们不妨用行递推。
所以我们设$ \ dp_{i,j,k} \ $表示当前放到第 \(i\) 行，有 \(j\) 列有1个棋子，有 \(k\) 列有2个棋子下的方案数。
容易写出转移方程如下：
1.若不放棋子
直接继承 \(dp_{i-1,j,k}\)
2.若放一个棋子
①若放在有零个棋子的列
\(dp_{i,j,k} \ += \ dp_{i-1,j-1,k} \ \times(m-j+1-k)\)
放在有零个棋子的列，那么现在和原来相比多了一个有一个棋子的列，所以\(j-1\)，而放在任意一个零列都可以，所以要乘\(m-j+1-k\)。
②若放在有一个棋子的列
\(dp_{i,j,k} \ += \ dp_{i-1,j+1,k-1} \ \times(j+1)\)
因为你放在有一个棋子的列，有一个棋子的列的数量就减一了，所以对应转移过来应该是加一，而放在这\(j+1\)列都可以，所以要乘\(j+1\)。
3.若放两个棋子
①若一个放在零个棋子的列，一个放在一个棋子的列
\(dp_{i,j,k} \ += \ dp_{i-1,j,k-1} \ \times(m-j-k+1)\times j\)
这样就会让两个棋子的列多出一个，所以\(k-1\)，而放在零个棋子的列有\(m-j-k+1\)，放在一个棋子的列有\(j\)，所以相乘。
②若两个都放在一个棋子的列
\(dp_{i,j,k} \ += \ dp_{i-1,j+2,k-2} \ \times\) \(j+2 \choose 2\)
j+2选2。
③若两个都放在零个棋子的列
\(dp_{i,j,k} \ += \ dp_{i-1,j-2,k} \ \times\)\(m-j-k+2\choose 2\)
同上。
再多显然不可能了。
讨论结束。
Code

#include<bits/stdc++.h>
using namespace std;
const int mod=9999973;
int n,m;
long long dp[105][105][105];
long long ans;
int main(){
	scanf("%d %d",&n,&m);
	dp[0][0][0]=1;
	for(int i=1;i<=n;++i){
		for(int j=0;j<=m;++j){
			for(int k=0;k<=m-j;++k){
				dp[i][j][k]=dp[i-1][j][k]%mod;
				if(j>=1) dp[i][j][k]+=dp[i-1][j-1][k]*(m-j-k+1)%mod,dp[i][j][k]%=mod;
				if(k>=1) dp[i][j][k]+=dp[i-1][j+1][k-1]*(j+1)%mod,dp[i][j][k]%=mod;
				if(k>=1) dp[i][j][k]+=(dp[i-1][j][k-1]*(m-j-k+1)%mod)*j%mod,dp[i][j][k]%=mod;
				dp[i][j][k]+=dp[i-1][j+2][k-2]*(j+2)*(j+1)/2%mod,dp[i][j][k]%=mod;
				if(j>=2) dp[i][j][k]+=dp[i-1][j-2][k]*(m-j-k+2)*(m-j-k+1)/2%mod,dp[i][j][k]%=mod;
			}
		}
	}
	for(int i=0;i<=m;++i){
		for(int j=0;j<=m;++j) ans+=dp[n][i][j],ans%=mod;
	}
	printf("%lld",ans);
	return 0;
}