【简●解】[AHOI2009]中国象棋

【题目大意】

叫你在\(n×m\)的棋盘上放若干个炮(可以是0个)，使得没有一个炮可以攻击到另一个炮，问有多少种放置方法。

【关键词】

\(DP\)
分类讨论
乘法和加法原理

【分析】

仔细观察就会发现，棋盘中每行，每列只有放\(0\)，\(1\)，\(2\)个三种方案。如果我们把状态量设为列，那么知道任意两种方案的列数，即可用总列数减去它得到另一种方案的列数。

我们设状态方程：\(f[i][j][k]\)，表示的是前\(i\)行，其中\(j\)列有\(1\)个棋子，\(k\)列有\(2\)个棋子的总方案数。

那么对于行的转移，我们有三种情况。

在第\(i\)行不放棋子。
在第\(i\)行放\(1\)个棋子。
在第\(i\)行放\(2\)个棋子。

不放棋子，即\(f[i][j][k]=f[i-1][j][k]\)。
放\(1\)个棋子，又分两种情况:
- 放在有\(1\)个棋子的列上，\(j+1\)列都可以放。即\(f[i][j][k]+=f[i-1][j+1][k-1]*(j+1)\)。
- 放在没有棋子的列上，\(m-(j-1)-k\)列都可放。即\(f[i][j][k]+=f[i-1][j-1][k]*(m-j-k+1)\)
放\(2\)个棋子，分三种情况:
- \(2\)个都放在没有棋子的列上。即\(f[i][j][k]+=f[i-1][j-2][k]*C_{m-(j-2)-k}^{2}\)。
- \(2\)个都放在有\(1\)个棋子的列上。即\(f[i][j][k]+=f[i-1][j+2][k-2]*C_{j+2}^2\)。
- \(1\)个放在没有棋子的列上，另一个放在有\(1\)个棋子的列上。即\(f[i][j][k]+=f[i-1][j][k-1]*(m-j-k+1)\)。

然后就可以\(A\)掉了，哦，记得开\(long long\)。。。

【Code】

#pragma GCC optimize("O3")

#pragma GCC optimize("O2")

#include<cstdio>

#include<cstdlib>

#include<cstring>

#define ll long long

#define R register

using namespace std;

const int MAX = 100 + 5;

const int mod = 9999973;

inline int read(){

	int f = 1, x = 0;char ch;

	do { ch = getchar(); if (ch == '-') f = -1; } while (ch < '0'||ch>'9');

	do {x = x*10+ch-'0'; ch = getchar(); } while (ch >= '0' && ch <= '9');

	return f*x;

}

inline ll c(ll x) {

	return (x * (x - 1) / 2) % mod;

}

int n, m;

ll f[MAX][MAX][MAX], ans;

int main(){

	n = read(), m = read();

	f[0][0][0] = 1;

	for (R int i = 1;i <= n; ++i) {

		for (R int j = 0;j <= m; ++j) {

			for (R int k = 0;k <= m - j; ++k) {

				f[i][j][k] = f[i-1][j][k];

				if (k > 0) {

					f[i][j][k] += (f[i-1][j+1][k-1] * (j+1)) % mod;

					f[i][j][k] %= mod;

					f[i][j][k] += (f[i-1][j][k-1] * j * (m-j-k+1)) %mod;

					f[i][j][k] %= mod;

				}

				if (j > 0) {

					f[i][j][k] += (f[i-1][j-1][k] * (m-j-k+1)) %mod;

					f[i][j][k] %= mod;

				}

				if (k > 1) {

					f[i][j][k] += (f[i-1][j+2][k-2] * c(j+2)) % mod;

					f[i][j][k] %= mod;

				}

				if (j > 1) {

					f[i][j][k] += (f[i-1][j-2][k] * c(m-j-k+2)) % mod;

					f[i][j][k] %= mod;

				}

			}

		}

	}

	for (R int i = 0;i <= m; ++i) {

		for (R int j = 0;j <= m; ++j) {

			ans += f[n][i][j];

			ans %= mod;

		}

	}

	printf("%lld", (ans + mod) % mod);

	return 0;

}

巴特西

【简●解】[AHOI2009]中国象棋

【题目大意】

【关键词】

【分析】

【Code】

最新文章

热门文章