动态规划 | AHOI2009 中国象棋

Description

这次小可可想解决的难题和中国象棋有关,在一个N行M列的棋盘上,让你放若干个炮(可以是0个),使得没有一个炮可以攻击到另一个炮,请问有多少种放置方法。大家肯定很清楚,在中国象棋中炮的行走方式是:一个炮攻击到另一个炮,当且仅当它们在同一行或同一列中,且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧!

Input

一行包含两个整数N,M,之间由一个空格隔开。

Output

总共的方案数,由于该值可能很大,只需给出方案数模9999973的结果。

Sample Input

1 3

Sample Output

7

Hint

样例说明

除了3个格子里都塞满了炮以外,其它方案都是可行的,所以一共有2×2×2-1=7种方案。

数据范围

100%的数据中N和M均不超过100

50%的数据中N和M至少有一个数不超过8

30%的数据中N和M均不超过6

分析

首先想到,每一行最多只能塞进 2 门炮,否则就会出现隔山打牛的情况了,那么每一行就只有 2 种合法状态,即放 1 门炮和放 2 门炮

设 $f[i][j][k]$ 表示到了第 $i$ 行,有 $j$ 列只有一门炮,还有 $k$ 列有两门炮的方案数,显然 $k\leq m-j$

那么剩下没有放炮的列数就是:$m-j-k$,接下来可以有 3 种选择:

  1. 在第 $i$ 行不放炮,此时状态继承了上一行的状态,即 $f[i][j][k]=f[i-1][j][k]$

  2. 在第 $i$ 行放一门炮,又有两种选择(不能放在有 2 门炮的列上面)
    • 放在只有一门炮的一列,会使它变成有 2 门炮,因此 $k$ 的状态需要从 $k-1$ 转移过来,而只有一门炮的列数会减少 1,而变成当前的 $j$ ,所以 $j$ 的状态从 $j+1$ 转移过来,既然是从 $j+1$ 转移过来,那么可以在这 $j+1$ 列上放炮,方案数乘上 $j+1$,即:$f[i][j][k]+=f[i-1][j+1][k-1]\times (j+1)$
    • 放在没有炮的一列,会使它变成有 1 门炮,因此 $j$ 的状态要从 $j-1$ 转移,此时 $k$ 状态不变,又因为当前没有放炮的列数是 $m-j-k$,注意空的列数是相对于 $j=j-1$ 的状态而言的,所以实际空的列数为 $m-(j-1)-k$,即:$f[i][j][k]+=f[i-1][j-1][k]\times (m-(j-1)-k)$
  3. 在第 $i$ 行放两门炮,有三种情况需要讨论:
    • 两门炮都放在没放炮的那一列,和上面的的思路类似,但是注意这 2 门炮的排列组合,可以得出:$f[i][j]+=f[i-1][j-2][k]\times C^2_{m-(j-2)-k}$
    • 两门炮都放在放了 1 门炮的那一列,也是排列组合,可以得出:$f[i][j]+=f[i-1][j+2][k-2]\times C^2_{j+2}$
    • 一门放在没放炮的一列,一门放在放了炮的一列,此时综合情况 2 的两种子情况可以得出:$f[i][j][k]+=f[i-1][j][k-1]\times j \times (m-(k-1)-j)$

边界为 $f[0][0][0]=1$,这便是 省选 / NOI- 的 DP 题难度吧,题面不长但是很烧脑子。。。

Codes

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define maxn 108
using namespace std;
typedef long long ll;
int n,m; const int mod=9999973;
long long f[maxn][maxn][maxn];
int c(int x){
	return ((x*(x-1))/2)%mod;
}
long long dp(){
	f[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++){
				f[i][j][k]=f[i-1][j][k];
                if(k>=1)(f[i][j][k]+=f[i-1][j+1][k-1]*(j+1));
                if(j>=1)(f[i][j][k]+=f[i-1][j-1][k]*(m-j-k+1));
                if(k>=2)(f[i][j][k]+=f[i-1][j+2][k-2]*(((j+2)*(j+1))/2));
                if(k>=1)(f[i][j][k]+=f[i-1][j][k-1]*j*(m-j-k+1));
                if(j>=2)(f[i][j][k]+=f[i-1][j-2][k]*c(m-j-k+2));
                f[i][j][k]%=mod;
			}
	long long ans=0;
	for(int i=0;i<=m;i++)
		for(int j=0;j<=m;j++)
			ans+=f[n][i][j],ans%=mod;
	return (ans+mod)%mod;
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("testin.txt","r",stdin);
	freopen("testout.txt","w",stdout);
	#endif
	scanf("%d%d",&n,&m);
	printf("%lld",dp());
	return 0;
}