「一本通 5.4 例 1」骑士

形式化题目

在 $n \times n$ 的棋盘上放 $k$ 个国王（King），国王攻击与它相邻的 $8$ 个格子（横、竖、斜方向各一格）。求使得任意两个国王无法互相攻击的放置方案总数。

正解

思路

1. 单行合法状态

国王攻击上下左右及四个斜角，因此同一行内不允许两个国王左右相邻。用二进制掩码 mask 表示一行的摆放，合法条件是：

\text{mask} \& (\text{mask} \gg 1) = 0

即不存在相邻的两位同时为 1。对 $n \le 9$ ，单行合法状态不超过 $O(2^n)$ 个，可以全部枚举出来。

2. 行间相容条件

相邻两行的状态 mask（上一行）与 nxt（下一行）相容，当且仅当两个国王不同列、不互处斜对角：

同列不冲突：mask & nxt == 0；
左斜不冲突：mask & (nxt >> 1) == 0；
右斜不冲突：mask & (nxt << 1) == 0。

这三个位运算判据一次性排除纵向与斜向攻击，预处理出每个状态的相容转移表。

3. 按国王数计数的 DP

设状态 $(used, mask)$ 表示已放置 $used$ 个国王且当前行状态为 $mask$ 的方案数。从第 0 行的哨兵状态 $(0, 0)$ 出发，逐行转移：

dp_{r+1}[(used + cnt(\text{nxt}), \text{nxt})] \mathrel{+}= dp_r[(used, mask)]

其中 cnt(nxt) 是 nxt 的置位数（该行国王数），且只转移到相容状态。最终答案是所有行处理完后 $used = k$ 的方案数之和。

由于答案可能很大（ $n = 9$ 时方案数可达 $10^9$ 量级），Python 的任意精度整数天然避免溢出。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 20:45
# update_at: 2026-09-30 20:45

import sys
from collections import defaultdict


def valid_states(n: int) -> list[tuple[int, int]]:
    """生成单行内不出现左右相邻国王的合法状态与国王数：(mask, bit_count)。"""
    return [
        (mask, mask.bit_count())
        for mask in range(1 << n)
        if not (mask & (mask >> 1))
    ]


def compatible_transitions(
    states: list[tuple[int, int]],
) -> dict[int, list[tuple[int, int]]]:
    """预处理每种行状态可以转移到的下一行相容状态（避开同列及斜对角攻击）。"""
    return {
        mask: [
            (nxt_mask, nxt_cnt)
            for nxt_mask, nxt_cnt in states
            # 同列不重叠、左斜不冲突、右斜不冲突
            if not (mask & nxt_mask)
            and not (mask & (nxt_mask >> 1))
            and not (mask & (nxt_mask << 1))
        ]
        for mask, _ in states
    }


def advance(
    dp: dict[tuple[int, int], int],
    adj: dict[int, list[tuple[int, int]]],
    limit: int,
) -> dict[tuple[int, int], int]:
    """推进一行状态：从上一行的 (已用国王数, 行状态) 转移到当前行。"""
    nxt: dict[tuple[int, int], int] = defaultdict(int)
    for (used, mask), ways in dp.items():
        for nxt_mask, nxt_cnt in adj[mask]:
            total_used = used + nxt_cnt
            if total_used <= limit:
                nxt[(total_used, nxt_mask)] += ways
    return nxt


def count_ways(n: int, k: int) -> int:
    """状压 DP 计算在 n*n 棋盘上放置 k 个互不攻击国王的方案总数。"""
    if k > (n + 1) // 2 * ((n + 1) // 2):  # 超过棋盘理论最多可放国王数（上界估算剪枝）
        pass  # 仍交给 DP 保证边界正确，或直接跑 DP

    states = valid_states(n)
    adj = compatible_transitions(states)

    dp: dict[tuple[int, int], int] = {(0, 0): 1}  # 第 0 行哨兵状态：0 个国王，空行 mask=0
    for _ in range(n):
        dp = advance(dp, adj, k)

    return sum(ways for (used, _), ways in dp.items() if used == k)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    tokens = list(data)
    if not tokens:
        return
    n, k = tokens[0], tokens[1]
    print(count_ways(n, k))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 11:17
 * update_at: 2026-10-05 11:17
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 11;
const int MAXK = 105;
const int MAXS = 1 << 10; // 单行状态掩码上限：n <= 10

int n, k;
int all_state[MAXS]; // 合法单行状态（行内无左右相邻国王）的掩码列表
int state_num;       // 合法状态个数
int kings[MAXS];     // kings[s]：状态 s 这一行的国王数（置位数）

// dp[cur][j][s]：处理到当前行、已放 j 个国王、当前行状态为 s 的方案数
// 用 0/1 两层滚动，cur 表示当前层
ll dp[2][MAXK][MAXS];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;

    // 预处理单行合法状态：国王攻击左右格，行内不能有相邻的 1
    for (int s = 0; s < (1 << n); s++) {
        if ((s & (s << 1)) == 0) {
            all_state[state_num] = s;
            // 统计该状态国王数
            int c = 0;
            for (int i = 0; i < n; i++) {
                if (s & (1 << i)) c++;
            }
            kings[s] = c;
            state_num++;
        }
    }

    int cur = 0;
    // 初始：还没放任何行，0 个国王，上一行（哨兵）状态为空
    dp[cur][0][0] = 1;

    for (int row = 1; row <= n; row++) {
        int nxt = cur ^ 1;
        // 先清空新一层
        for (int j = 0; j <= k; j++) {
            for (int a = 0; a < state_num; a++) {
                dp[nxt][j][all_state[a]] = 0;
            }
        }
        // 枚举上一行状态 a、当前行状态 b，相容则转移
        for (int a = 0; a < state_num; a++) {
            int sa = all_state[a];
            for (int b = 0; b < state_num; b++) {
                int sb = all_state[b];
                // 同列不冲突、左斜不冲突、右斜不冲突
                if (sa & sb) continue;
                if (sa & (sb << 1)) continue;
                if (sa & (sb >> 1)) continue;
                for (int j = 0; j + kings[sb] <= k; j++) {
                    dp[nxt][j + kings[sb]][sb] += dp[cur][j][sa];
                }
            }
        }
        cur = nxt;
    }

    // 答案：所有行处理完后恰好放了 k 个国王的所有方案
    ll ans = 0;
    for (int a = 0; a < state_num; a++) {
        ans += dp[cur][k][all_state[a]];
    }
    cout << ans << "\n";

    return 0;
}

复杂度

时间复杂度：设合法状态数为 $S$ （ $S \le 2^n$ ，实际上远小于，例如 $n=9$ 时 $S=89$ ）。状态对相容预处理的转移总量为 $O(S^2)$ ，DP 主循环为 $O(n \cdot S \cdot S_{\text{adj}} \cdot k)$ ，其中 $S_{\text{adj}}$ 是每个状态的平均相容状态数。对 $n \le 9, k \le n^2$ ，总运算量在 $10^6$ 量级，Python 轻松通过。
空间复杂度： $O(S \cdot k)$ ，使用滚动字典存储当前行状态，开销极小。

总结

国王放置问题的标准解法是逐行状压 DP：单行内禁止左右相邻，行间用三个位运算（同列、左斜、右斜）判相容。
把"已放国王数"并入 DP 状态，一遍 DP 即可统计恰好 $k$ 个国王的方案数。
Python 位运算与任意精度整数让计数实现非常直接，无需处理溢出。