自动搬运

查看原文

来自洛谷，原作者为

	lottle1212 **

搬运于2025-08-24 22:42:09，当前版本为作者最后更新于2023-06-05 11:44:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题传送门

Part 0

这是一道状态压缩 $\text{DP}$。

在尝试此题之前，建议大家先去完成 P1896 [SCOI2005] 互不侵犯，与此题类似，可以让大家对状态压缩 $\text{DP}$ 有一个初步的了解，也为此题作铺垫。

注：这篇题解并不会非常详细地去讲解状态压缩的原理，只是在 P1896 的基础上来解决此题。

Part 1

这一题中，需要我们求在 $N \times M (1 \leq N \leq 6, 1 \leq M \leq 100)$ 的棋盘上摆 $K (1 \leq K \leq 20)$ 个马的方案数。由于 $N$ 不超过 $6$，我们先枚举每一列的 $2 ^ N$ 个放马方案，用 $1$ 表示放马， $0$ 表示不放，并统计每一个放法中 $1$ 的个数（也就是马的个数）。到此为止，做法与 P1896 完全相同。

接下来就是转移状态了。P1896 中只需考虑前一行的状态，所以用 位置、方案、个数 来表示答案。而本题需要考虑前两行的状态，需要多加一维，以 位置、前列方案、本列方案、个数 来表示答案。

然后通过五层循环 位置、本列方案、个数、前列方案、前前列方案 来进行状态转移。注意：这里要判断三行中会不会有马互相攻击。最后别忘把答案对 $10^9 + 7$ 取模。

AC Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int mxn = 100, mxm = 1 <<6;
const int N = mxn + 10, M = mxm + 10;
int n, m, K, num[M], dp[N][M][M][30], ans;
int get_val(int x) {
	int sum = 0;
	while(x) sum += x & 1, x >>= 1;
	return sum;
} // 求出马的个数
signed main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m >> K;
	for(int i = 0; i ^ (1 << n); ++ i) num[i] = get_val(i), dp[1][0][i][num[i]] = 1; // 预处理马的个数
	for(int i = 2; i <= m; ++ i) // 列
		for(int j = 0; j ^ (1 << n); ++ j) // 本列状态
			for(int h = num[j]; h <= K; ++ h) // 马的个数
				for(int k = 0; k ^ (1 << n); ++ k) // 前前列状态
					for(int l = 0; l ^ (1 << n); ++ l) // 前列状态
						if(! ((j & (k << 1)) || (j & (k >> 1)) || (j & (l << 2)) || (j & (l >> 2)) || (l & (k << 2)) || (l & (k >> 2)))) // 判断条件是否满足
							dp[i][l][j][h] = (dp[i][l][j][h] + dp[i - 1][k][l][h - num[j]]) % mod; //进行转移
	for(int i = 0; i ^ (1 << n); ++ i)
		for(int j = 0; j ^ (1 << n); ++ j)
			ans = (ans + dp[m][i][j][K]) % mod;
	cout << ans << '\n';
	return 0;
}