【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\n",ans);

	return 0;

}