![【BZOJ】1801 [Ahoi2009]chess 中国象棋(dp) 【BZOJ】1801 [Ahoi2009]chess 中国象棋(dp)](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
题目
传送门:QWQ
分析
发现我们关心的不是棋子的位置,我们只关心棋子数量就ok。
首先每行每列最多两个棋子。这是显然的。
然后我觉得本题最难的部分就是对行进行讨论,蒟蒻我一直被限制在了对格点讨论。。。。
$dp[i][j][k] $放了前$i$行,有$j$列有1个棋子,有$k$列有2个棋子。转移就很显然了。
代码
#include <bits/stdc++.h>
typedef long long ll;
const int maxn=;const ll MOD=; ll dp[maxn][maxn][maxn];
//dp[i][j][k] 放了前i行,有j列有1个棋子,有k列有2个棋子
ll num(int x){return ll(x)*ll(x-)/;}
using namespace std;
int main(){
int n,m;scanf("%d%d",&n,&m);
dp[][][]=;
for(int i=;i<n;i++){ //放第i+1行
for(int j=;j<=m;j++){
for(int k=;k+j<=m;k++){
dp[i+][j][k]=(dp[i+][j][k]+dp[i][j][k])%MOD;
if(m-j-k>=) dp[i+][j+][k]=(dp[i+][j+][k]+dp[i][j][k]*(m-j-k))%MOD;
if(j>=) dp[i+][j-][k+]=(dp[i+][j-][k+]+dp[i][j][k]*j)%MOD;
if(m-j-k>=) dp[i+][j+][k]=(dp[i+][j+][k]+dp[i][j][k]*num(m-j-k))%MOD;
if(j>=) dp[i+][j-][k+]=(dp[i+][j-][k+]+dp[i][j][k]*num(j))%MOD;
if(m-j-k>= && j>=) dp[i+][j][k+]=(dp[i+][j][k+]+dp[i][j][k]*(m-j-k)*j)%MOD;
}
}
}
ll ans=;
for(int i=;i<=m;i++)
for(int j=;j+i<=m;j++)
ans=(ans+dp[n][i][j])%MOD;
printf("%lld\n",ans);
return ;
}