把每一列压成二进制状态，利用马只会影响前两列的性质，做记录前两列状态和已放马数量的轮廓 DP。
OJ: luogu
题目 ID: P8756
难度:提高+/省选-
标签:状态压缩动态规划轮廓DP计数dp
日期: 2026-06-21 05:26
题意
在 N x M 的棋盘上放 K 个马，要求任意两个马都不能互相攻击。
问方案数，对 1e9+7 取模。
思路
先看一个小数据暴力：
cpp
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
int n, m, k_need;
int board[10][105];
long long ans;
int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
bool ok_place(int x, int y) {
for (int i = 0; i < 8; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && board[nx][ny]) {
return false;
}
}
return true;
}
void dfs_cell(int pos, int used) {
if (used > k_need) {
return;
}
if (pos == n * m) {
if (used == k_need) {
ans++;
}
return;
}
int x = pos % n + 1;
int y = pos / n + 1;
dfs_cell(pos + 1, used);
if (ok_place(x, y)) {
board[x][y] = 1;
dfs_cell(pos + 1, used + 1);
board[x][y] = 0;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// brute.cpp：小数据直接枚举每个格子放不放马。
cin >> n >> m >> k_need;
memset(board, 0, sizeof(board));
ans = 0;
dfs_cell(0, 0);
cout << ans % MOD << '\n';
return 0;
}暴力就是逐格枚举放不放马，再检查是否合法。
正解要利用 N<=6 很小这一点，把“一整列”压成一个二进制状态。
关键观察是：
- 当前列只会和前一列、前两列发生马的攻击关系
- 更早的列不会再影响当前列
因此状态中只需要记住：
- 前两列的摆放情况
- 已经放了多少个马
设列状态为 s。
预处理两种合法性：
ok1[a][b]：相邻两列a,b是否冲突ok2[a][b]：相隔两列a,b是否冲突
然后做按列推进的 DP：
dp[col][pre2][pre1][used]
DP 转移方程
枚举当前列状态 cur，若它和前两列都不冲突，则：
其中合法条件是 ok1[pre1][cur] 且 ok2[pre2][cur]。
每次枚举当前列状态 cur，只要满足：
ok1[pre1][cur]ok2[pre2][cur]
就能转移。
这就是典型的“小行数、大列数”的轮廓 DP。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
const int MAXS = 1 << 6;
int n, m, k_need;
int bit_cnt[MAXS];
int ok1[MAXS][MAXS];
int ok2[MAXS][MAXS];
int valid_next[MAXS][MAXS][MAXS];
int valid_cnt[MAXS][MAXS];
int dp[2][MAXS][MAXS][25];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> k_need;
int full = 1 << n;
for (int s = 0; s < full; s++) {
bit_cnt[s] = __builtin_popcount((unsigned int) s);
}
int row_mask = full - 1;
for (int a = 0; a < full; a++) {
int attack_adj = ((a << 2) | (a >> 2)) & row_mask;
int attack_far = ((a << 1) | (a >> 1)) & row_mask;
for (int b = 0; b < full; b++) {
ok1[a][b] = ((attack_adj & b) == 0);
ok2[a][b] = ((attack_far & b) == 0);
}
}
for (int p2 = 0; p2 < full; p2++) {
for (int p1 = 0; p1 < full; p1++) {
valid_cnt[p2][p1] = 0;
for (int cur = 0; cur < full; cur++) {
if (ok1[p1][cur] && ok2[p2][cur]) {
valid_next[p2][p1][valid_cnt[p2][p1]++] = cur;
}
}
}
}
memset(dp, 0, sizeof(dp));
dp[0][0][0][0] = 1;
for (int col = 0; col < m; col++) {
int now = col & 1;
int nxt = now ^ 1;
memset(dp[nxt], 0, sizeof(dp[nxt]));
for (int p2 = 0; p2 < full; p2++) {
for (int p1 = 0; p1 < full; p1++) {
for (int used = 0; used <= k_need; used++) {
int ways = dp[now][p2][p1][used];
if (ways == 0) {
continue;
}
for (int idx = 0; idx < valid_cnt[p2][p1]; idx++) {
int cur = valid_next[p2][p1][idx];
int nused = used + bit_cnt[cur];
if (nused > k_need) {
continue;
}
int &ref = dp[nxt][p1][cur][nused];
ref += ways;
if (ref >= MOD) {
ref -= MOD;
}
}
}
}
}
}
int last = m & 1;
int ans = 0;
for (int p2 = 0; p2 < full; p2++) {
for (int p1 = 0; p1 < full; p1++) {
ans += dp[last][p2][p1][k_need];
if (ans >= MOD) {
ans -= MOD;
}
}
}
cout << ans << '\n';
return 0;
}复杂度
时间复杂度约为 N<=6，状态数很小，可以通过。
总结
这题的关键是识别马的攻击范围只跨 1 列和 2 列，因此状态只需要保留前两列。 看清这一点后，问题就会自然落到列状压 DP 上。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
