LGOJP2051 [AHOI2009]中国象棋

比较明显的计数dp。不知道为什么被打了状压的tag...

不难发现无论炮放在哪里其实是等价的，需要知道的只有这一列放了一个炮还是两个炮还是还没放，那么可以设\(f[i,j,k]\)表示第\(i\)行，一共有\(j\)列放了两个炮，\(k\)列放了一个炮。

然后转移考虑一下选数的组合意义即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 100010;

const int mod = 9999973;

int n, m, fac[N], inv[N];

int f[110][110][110];

// f[i][j][k] 表示前i行，然后有j列放了两个，k列放了一个

int power(int a, int b) {

	int ans = 1;

	while(b) {

		if(b & 1) ans = 1ll * ans * a % mod;

		a = 1ll * a * a % mod; b >>= 1;

	}

	return ans;

}

int C(int n, int m) {

	if(n > m) return 0;

	return 1ll * fac[m] * inv[m - n] % mod * inv[n] % mod;

}

int main() {

	scanf("%d%d", &n, &m);

	fac[0] = inv[0] = 1;

	for(int i = 1; i < N; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;

	for(int i = 1; i < N; ++i) inv[i] = power(fac[i], mod - 2);

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

	for(int i = 0; i < n; ++i)

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

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

				if(f[i][j][k]) {

					// 不放

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

					// 放一个

					if(k + 1 <= m) (f[i + 1][j][k + 1] += 1ll * f[i][j][k] * C(1, m - j - k) % mod) %= mod;

					if(j + 1 <= m && k) (f[i + 1][j + 1][k - 1] += 1ll * f[i][j][k] * C(1, k) % mod) %= mod;

					// 放两个

					if(j + 2 <= m && k >= 2) (f[i + 1][j + 2][k - 2] += 1ll * f[i][j][k] * C(2, k) % mod) %= mod;

					if(k + 2 <= m) (f[i + 1][j][k + 2] += 1ll * f[i][j][k] * C(2, m - j - k) % mod) %= mod;

					if(j + 1 <= m) (f[i + 1][j + 1][k] += 1ll * f[i][j][k] * C(1, m - j - k) % mod * C(1, k) % mod)  %= mod;

				}

	int ans = 0;

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

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

			(ans += f[n][i][j]) %= mod;

//			printf("%d %d %d\n", i, j, f[n][i][j]);

		}

	}

//	puts("");

	printf("%d\n", ans);

}

巴特西

LGOJP2051 [AHOI2009]中国象棋

最新文章

热门文章