bzoj1801 /AHOI2009 中国象棋

题目描述

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

输入格式

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

输出格式

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

输入输出样例

输入 #1

1 3

输出 #1

7

说明/提示

样例说明

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

数据范围

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

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

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

分析

注意到，炮互不攻击的条件等价于每行每列的炮都不超过2个。以此为基础设计状态。我们考虑逐行放炮，炮放在哪一列显然只和那一列的炮数有关，而每一列都是独立的，因此我们并不需要记录每一列的炮数，只需要记录那些列有1个炮，那些列有2个炮，剩下的就都是0个炮。
于是我们用 $f\left[i\right]\left[j\right]\left[k\right]$f[i][j][k] 表示 到了第 $i$i 行， 有 $j$j 列 放了 1个炮， 有 $k$k 列放了两个炮的方案数。
考虑怎么转移。
第 $i$i 行能放的炮只有 0,1,2个，我们分别考虑这三种情况。
①：不放
$f\left[i\right]\left[j\right]\left[k\right]=f[i-1]\left[j\right]\left[k\right]$f[i][j][k]=f[i−1][j][k]
②：放 $1$1 个
Ⅰ：放在空的列里
$f\left[i\right]\left[j\right]\left[k\right]=f[i-1][j-1]\left[k\right]\ast (m-j-k+1)$f[i][j][k]=f[i−1][j−1][k]∗(m−j−k+1)
Ⅱ：放在 有 1 个炮的列里
$f\left[i\right]\left[j\right]\left[k\right]=f\left[i\right]\left[j\right]\left[k\right]+f[i-1][j+1][k-1]\ast (j+1)$f[i][j][k]=f[i][j][k]+f[i−1][j+1][k−1]∗(j+1)
③：放 2 个
Ⅰ：放在两个空的列里（C是组合数）
$f\left[i\right]\left[j\right]\left[k\right]=f\left[i\right]\left[j\right]\left[k\right]+f[i-1][j-2]\left[k\right]\ast c[m-j-k+2]\left[2\right]$f[i][j][k]=f[i][j][k]+f[i−1][j−2][k]∗c[m−j−k+2][2]
Ⅱ：1个放在空的列里，1个放在有1个炮的列里
$f\left[i\right]\left[j\right]\left[k\right]=f\left[i\right]\left[j\right]\left[k\right]+f[i-1]\left[j\right][k-1]\ast (m-j-k+1)\ast j$f[i][j][k]=f[i][j][k]+f[i−1][j][k−1]∗(m−j−k+1)∗j
Ⅲ：放在 2 列有 1 个炮的列里
$f\left[i\right]\left[j\right]\left[k\right]=f\left[i\right]\left[j\right]\left[k\right]+f[i-1][j+2][k-2]\ast c[j+2]\left[2\right]$f[i][j][k]=f[i][j][k]+f[i−1][j+2][k−2]∗c[j+2][2]

代码如下

#include <bits/stdc++.h>
#define mod 9999973
#define LL long long
using namespace std;
int f[104][104][104], c[104][104], ans;
LL z = 1;
int main(){
	int i, j, k, n, m;
	scanf("%d%d", &n, &m);
	f[0][0][0] = 1;
	for(i = 0; i <= 100; i++){
		c[i][0] = 1;
		for(j = 1; j <= i; j++) c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
	}
	for(i = 1; i <= n; i++){
		for(j = 0; j <= m; j++){
			for(k = 0; k + j <= m; k++){
				f[i][j][k] = f[i-1][j][k];
				if(j >= 1){
					f[i][j][k] = (f[i][j][k] + z * f[i-1][j-1][k] * (m - j - k + 1) % mod) % mod;
					if(j >= 2) f[i][j][k] = (f[i][j][k] + z * f[i-1][j-2][k] * c[m - j - k + 2][2] % mod) % mod;  
				}
				if(k >= 1){
					f[i][j][k] = (f[i][j][k] + z * f[i-1][j+1][k-1] * (j+1) % mod) % mod;
					f[i][j][k] = (f[i][j][k] + z * f[i-1][j][k-1] * (m - j - k + 1) % mod * j % mod) % mod;
					if(k >= 2) f[i][j][k] = (f[i][j][k] + z * f[i-1][j+2][k-2] * c[j+2][2] % mod) % mod;
				}
			}
		}
	}
	for(i = 0; i <= m; i++)
		for(j = 0; j + i <= m; j++) ans = (ans + f[n][i][j]) % mod;
	printf("%d", ans);
	return 0;
}