1801: [Ahoi2009]chess 中国象棋
题目：传送门
题解：
表示自己的DP菜的抠脚
%题解...
定义f[i][j][k]表示前i行 仅有一个棋子的有j列 有两个棋子的有k个 的方案数 （对于任意的一行或者一列，棋子数都不会超过2）
那么以下的转移其实就很容易YY了：
对于当前的第i行，一共分为6种情况：
1、啥玩意儿都不填 f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k]*(m-j+1-k))%mod;
2、只填一个棋子，并且填在当前没有棋子的一列 f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k]*(m-j+1-k))%mod;
因为对于上一个状态来说，只有一个棋子的就多了一列啊
3、只填一个棋子，并且填在当前仅有一个棋子的一列 f[i][j][k]=(f[i][j][k]+f[i-1][j+1][k-1]*(j+1))%mod;
很明显两个棋子的列数多了一，且一个棋子的列数少了一
以下三种和前面的都一样，就不解释了：
4、填两个棋子，并且都填在当前没有棋子的列上 f[i][j][k]=(f[i][j][k]+f[i-1][j-2][k]*calc(m-j+2-k))%mod;
5、填两个棋子，一个填在有一个棋子的列上，一个填在没有棋子的列上 f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1]*j*(m-j-k+1))%mod;
6、填两个棋子，都填在有一个棋子的列上 f[i][j][k]=(f[i][j][k]+f[i-1][j+2][k-2]*calc(j+2))%mod;
PS：calc(int x){return x*(x-1)/2;}
代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define qread(x) x=read()
using namespace std;
typedef long long LL;
const LL mod=;
inline int read()
{
int f=,x=;char ch;
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return f*x;
}
int n,m;
LL f[][][];//f[i][j][k] 表示前i行 仅有一个棋子的有j列 有两个棋子的有k个 的方案数
LL calc(int x){return x*(x-)/;}
int main()
{
qread(n);qread(m);
memset(f,,sizeof(f));
f[][][]=1LL;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
for(int k=;k<=m-j;k++)
{
f[i][j][k]=f[i-][j][k];
if(j>)f[i][j][k]=(f[i][j][k]+f[i-][j-][k]*(m-j+-k))%mod;
if(k>)f[i][j][k]=(f[i][j][k]+f[i-][j+][k-]*(j+))%mod;
if(j>)f[i][j][k]=(f[i][j][k]+f[i-][j-][k]*calc(m-j+-k))%mod;
if(j> && k>)f[i][j][k]=(f[i][j][k]+f[i-][j][k-]*j*(m-j-k+))%mod;
if(k>)f[i][j][k]=(f[i][j][k]+f[i-][j+][k-]*calc(j+))%mod;
}
LL ans=;
for(int j=;j<=m;j++)
for(int k=;k<=m-j;k++)
ans=(ans+f[n][j][k])%mod;
printf("%lld\n",ans);
return ;
}
感觉很毒瘤。。。