【BZOJ1801】【AHOI2009】中国象棋（动态规划）
题面
题目描述
这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧！
输入格式：
一行包含两个整数N，M，之间由一个空格隔开。
输出格式：
总共的方案数，由于该值可能很大，只需给出方案数模9999973的结果。
输入样例#1：
1 3
输出样例#1：
7
题解
诶，我越来越菜了
这种傻逼题都不会做了。。。。
脑洞越来越小了。。。
很显然的，每行每列只能放两个炮
设(f[i][j][k])表示当前做到了第(i)行，有(j)列有一个炮，有(k)列有两个炮
直接转移就可以了。。。
中间稍微组合数算一下就行了。。。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define MAX 200
#define MOD 9999973
inline int read()
{
int x=0,t=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
int n,m;
int f[MAX][MAX][MAX];
int C(int n){return (1LL*n*(n-1)/2)%MOD;}
int main()
{
n=read();m=read();
f[0][0][0]=1;
for(int i=1;i<=n;++i)
for(int j=0;j<=m;++j)
for(int k=0;k+j<=m;++k)
{
f[i][j][k]=f[i-1][j][k];//不放炮
if(k)f[i][j][k]=(f[i][j][k]+1LL*f[i-1][j+1][k-1]*(j+1)%MOD)%MOD;//放一个炮
if(j)f[i][j][k]=(f[i][j][k]+1LL*f[i-1][j-1][k]*(m-k-j+1)%MOD)%MOD;//放一个炮
if(k>=2)f[i][j][k]=(f[i][j][k]+1LL*f[i-1][j+2][k-2]*C(j+2)%MOD)%MOD;//放两个炮
if(j>=2)f[i][j][k]=(f[i][j][k]+1LL*f[i-1][j-2][k]*C(m-k-j+2))%MOD;//放两个炮
if(j&&k)f[i][j][k]=(f[i][j][k]+1LL*f[i-1][j][k-1]*(m-k+1-j)*j%MOD)%MOD;//放两个炮
}
int ans=0;
for(int j=0;j<=m;++j)
for(int k=0;k+j<=m;++k)
ans=(ans+f[n][j][k])%MOD;
printf("%d
",ans);
return 0;
}