P1896 互不侵犯 · 习题解析｜信息学奥赛算法练功房

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P1896，日期见页头。两边不一致时信原站。

题目描述

在 N × N 的棋盘里面放 K 个国王，使他们互不攻击，共有多少种摆放方案。

国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 8 个格子。

输入格式

只有一行，包含两个数 N, K。

输出格式

所得的方案数。

说明/提示

数据范围及约定

对于全部数据，1 ≤ N ≤ 9，0 ≤ K ≤ N × N。

upd 2018.4.25：数据有加强。

输入输出样例

输入

3 2

输出

3 × 3 的棋盘放 2 个国王，16 种。

★ 这一组样例把本页三个错法全挡住了（忘了斜上方 24、至多 K 个 26、int 版在这个规模上不溢出所以是 16 —— ⚠ 严格说它是放过了 int 那个）。

1★★ 和上一道 P1879 只差两处，而两处都很典型

★ f[i][j][S] —— 多出来的那一维 j 是「已经放了几个」

    f[i][j][S] = 前 i 行放好、一共放了 j 个国王、第 i 行摆法恰好是 S 时的方案数
    f[i][j][S] = Σ f[i-1][j-|S|][T]

和上一道 P1879 的差别只有两处：

	P1879（奶牛）	P1896（国王）
冲突范围	四连通（只忌讳公共边）	★ 八连通（斜着也不行）
要数什么	所有方案	★ 恰好 `K` 个 ⇒ 多一维 `j`

⇒ 上下两行的判断从一条变成三条：S & T、S & (T << 1)、S & (T >> 1)。

p1896.cpp★ 这一版就能 AC

// P1896 互不侵犯 —— 正解：按行状压 DP ＋ 多一维「已经放了几个」
//
//   f[i][j][S] = 前 i 行放好了、一共放了 j 个国王、第 i 行的摆法恰好是 S 时的方案数
//   f[i][j][S] = Σ f[i-1][j - |S|][T]      要求 (S & T) == 0 且 (S & (T<<1)) == 0 且 (S & (T>>1)) == 0
//
// ★ 和上一道 [P1879] 的差别只有两处，但两处都很典型：
//   ① **多一维 j**（要恰好 K 个）—— 这就是「答案要计数到某个具体数量」时的标准做法；
//   ② 国王是**八连通**，所以上下两行不仅不能正对着，**斜着也不行**
//      ⇒ 三个条件：S & T、S & (T<<1)、S & (T>>1)。
//
// ★★ 而这道题上，「先把合法行筛出来」比上一道值钱：
//    n = 9 时 2⁹ = 512 个 S，同行合法的只有 **89** 个（正是斐波那契）。
// ⚠ 但**省多少倍要看你筛的是哪一侧**（实测，不是估）：
//    只筛内层那一侧 ⇒ **5.75 倍**（512 / 89）；两侧都筛才是 512² / 89² ≈ 33 倍。
//    ⇒ 又一次「换尺子结论不同」—— 报倍数时要说清楚量的是哪一段。
//
// ⚠ 答案会超 int：n = 9、K = 8 时方案数已经 8 位数往上，顶格更大 ⇒ **long long**。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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

    int n, K;
    if (!(cin >> n >> K)) return 0;

    // ★ 先把「同一行内合法」的摆法筛出来，连同它的国王数
    vector<int> st;
    vector<int> num;
    for (int S = 0; S < (1 << n); S++) {
        if (S & (S << 1)) continue;                  // 同行左右相邻
        st.push_back(S);
        num.push_back(__builtin_popcount((unsigned)S));
    }
    int m = (int)st.size();

    // f[j][k] = 放了 j 个国王、当前行摆法是第 k 个合法行
    vector<vector<ll>> f(K + 1, vector<ll>(m, 0)), g(K + 1, vector<ll>(m, 0));
    for (int k = 0; k < m; k++)
        if (num[k] <= K) f[num[k]][k] = 1;           // 第 1 行

    for (int i = 2; i <= n; i++) {
        for (auto& r : g) fill(r.begin(), r.end(), 0LL);
        for (int k = 0; k < m; k++) {                // 这一行摆 st[k]
            int S = st[k], c = num[k];
            for (int t = 0; t < m; t++) {            // 上一行摆 st[t]
                int T = st[t];
                if (S & T) continue;                 // 正上方
                if (S & (T << 1)) continue;          // 左上
                if (S & (T >> 1)) continue;          // 右上
                for (int j = c; j <= K; j++) g[j][k] += f[j - c][t];
            }
        }
        f.swap(g);
    }

    ll ans = 0;
    for (int k = 0; k < m; k++) ans += f[K][k];
    cout << ans << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

2★★ 第一个错法：把上一道的转移原样搬过来（忘了斜上方）

p1896NoDiag.cpp✗ 只判了正上方

// ✗ P1896：只判了「正上方」，忘了斜上方
//
// ★ 这是把上一道 [P1879 Corn Fields] 的转移原样搬过来的直接后果：
//   那道题的奶牛只忌讳**有公共边**（四连通），而国王是**八连通**。
// ⇒ 少了两条限制 ⇒ 它数的是正解的**超集** ⇒ 答案**恒 ≥ 正解**。
// ⚠ 又一次「同一张题单里，上一道的正确写法就是这一道的 bug」（[P1352] 那条）。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, K;
    if (!(cin >> n >> K)) return 0;
    vector<int> st, num;
    for (int S = 0; S < (1 << n); S++) {
        if (S & (S << 1)) continue;
        st.push_back(S);
        num.push_back(__builtin_popcount((unsigned)S));
    }
    int m = (int)st.size();
    vector<vector<ll>> f(K + 1, vector<ll>(m, 0)), g(K + 1, vector<ll>(m, 0));
    for (int k = 0; k < m; k++) if (num[k] <= K) f[num[k]][k] = 1;
    for (int i = 2; i <= n; i++) {
        for (auto& r : g) fill(r.begin(), r.end(), 0LL);
        for (int k = 0; k < m; k++) {
            int S = st[k], c = num[k];
            for (int t = 0; t < m; t++) {
                if (S & st[t]) continue;             // ← 只判了正上方
                for (int j = c; j <= K; j++) g[j][k] += f[j - c][t];
            }
        }
        f.swap(g);
    }
    ll ans = 0;
    for (int k = 0; k < m; k++) ans += f[K][k];
    cout << ans << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

少了两条限制 ⇒ 它数的是正解的超集 ⇒ 恒 ≥ 正解（300 / 300），被抓 147 / 300。 ★ 官方样例挡住了它（24 vs 16）。

⚠ 这是同一张题单里，上一道的正确写法就是这一道的 bug —— 本轮第三次（P1171 → P1433 是「回不回起点」，第 27 章 P2016 → P1352 是编号基）。 ⇒ ★★ 题单把它们排在一起，恰恰是因为它们不一样。

3★★★ 第二个错法：「恰好 K 个」读成「至多 K 个」—— 而它有个结构性盲区

p1896AtMost.cpp✗ 把 f[≤K] 全加起来

// ✗ P1896：把「恰好 K 个」读成了「至多 K 个」
//
// ★ 它把 f[≤K] 全加起来 ⇒ 它数的是正解的**超集** ⇒ 恒 ≥ 正解。
// ⚠ 而这个错法有一个**结构性的盲区**：K = 0 时「至多 0 个」和「恰好 0 个」是同一件事
//   ⇒ 那一档是精确的 0。题面 `0 ≤ K ≤ N×N` **明写着 K 可以是 0**，
//   而顺手写的生成器多半从 1 开始。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, K;
    if (!(cin >> n >> K)) return 0;
    vector<int> st, num;
    for (int S = 0; S < (1 << n); S++) {
        if (S & (S << 1)) continue;
        st.push_back(S);
        num.push_back(__builtin_popcount((unsigned)S));
    }
    int m = (int)st.size();
    vector<vector<ll>> f(K + 1, vector<ll>(m, 0)), g(K + 1, vector<ll>(m, 0));
    for (int k = 0; k < m; k++) if (num[k] <= K) f[num[k]][k] = 1;
    for (int i = 2; i <= n; i++) {
        for (auto& r : g) fill(r.begin(), r.end(), 0LL);
        for (int k = 0; k < m; k++) {
            int S = st[k], c = num[k];
            for (int t = 0; t < m; t++) {
                int T = st[t];
                if (S & T) continue;
                if (S & (T << 1)) continue;
                if (S & (T >> 1)) continue;
                for (int j = c; j <= K; j++) g[j][k] += f[j - c][t];
            }
        }
        f.swap(g);
    }
    ll ans = 0;
    for (int j = 0; j <= K; j++)                     // ← 把 ≤ K 的全加了
        for (int k = 0; k < m; k++) ans += f[j][k];
    cout << ans << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★★ K = 0 那一档是精确的 0，而题面明写着 K 可以是 0

它数的同样是超集 ⇒ 恒 ≥ 正解（300 / 300），被抓 221 / 300。


默认档（`K` 从 0 开始）里 `K = 0` 的轮数	79
其中它被抓	★ 0 —— 精确的 0
⚠ 换成「`K` 从 1 开始」的生成器	被抓 300 / 300

为什么：K = 0 时「至多 0 个」和「恰好 0 个」是同一件事 ⇒ 它压根没错。

⚠⚠ 而值得注意的是方向：这一次是「顺手写的生成器」反而更强 —— K 从 1 开始的那版 300/300 全抓，含 K = 0 的那版只有 221。 ⇒ ★★ 这和本书前面反复说的「顺手的默认值是藏身处」不矛盾，是同一件事的另一面： 生成器的档位分布决定抓获率，而它和「哪一档更像真实测试数据」是两回事 —— 题面写着 0 ≤ K，评测数据里就可能有 K = 0，那一档你必须测，哪怕它抓不到这个 bug。

4★★★ 第三个错法：int —— 而「要不要 long long」是搜得出来的，不用猜

p1896Int.cpp✗ 方案数用了 int

// ✗ P1896：方案数用了 int
//
// ⚠ 顶格 n = 9 时最大的方案数出现在 K = 20 附近，是 8 位数往上 ——
//    ★ 这一页把「到底哪一个 (n, K) 第一次撑破 int」直接搜出来了（见 Count 第 ④ 段），
//      而不是「感觉可能会爆，那就开 long long 吧」。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, K;
    if (!(cin >> n >> K)) return 0;
    vector<int> st, num;
    for (int S = 0; S < (1 << n); S++) {
        if (S & (S << 1)) continue;
        st.push_back(S);
        num.push_back(__builtin_popcount((unsigned)S));
    }
    int m = (int)st.size();
    vector<vector<int>> f(K + 1, vector<int>(m, 0)), g(K + 1, vector<int>(m, 0));   // ← int
    for (int k = 0; k < m; k++) if (num[k] <= K) f[num[k]][k] = 1;
    for (int i = 2; i <= n; i++) {
        for (auto& r : g) fill(r.begin(), r.end(), 0);
        for (int k = 0; k < m; k++) {
            int S = st[k], c = num[k];
            for (int t = 0; t < m; t++) {
                int T = st[t];
                if (S & T) continue;
                if (S & (T << 1)) continue;
                if (S & (T >> 1)) continue;
                for (int j = c; j <= K; j++) g[j][k] += f[j - c][t];
            }
        }
        f.swap(g);
    }
    int ans = 0;
    for (int k = 0; k < m; k++) ans += f[K][k];
    cout << ans << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★ 把 (n, K) 全部 385 组跑一遍，两个数字直接落地

题面对答案的大小一个字都没说。那就自己算 —— 1 ≤ N ≤ 9、0 ≤ K ≤ N²，一共只有几百组，全跑一遍：


★ 全局最大方案数	`n = 9`、`K = 13` 时 57 647 295 377
它是 `int` 上限的	★ 26.84 倍
★ 第一个撑破 `int` 的 `(n, K)`	`n = 9`、`K = 9`

⇒ ★★ 这就是第 16 章 P1002 那条「输入空间小的时候，「算一遍」比「对拍」又快又充分」的又一次现场：n ≤ 9 意味着整个输入空间只有 385 组， 与其猜「会不会爆」，不如把它数完。

5★ 「先筛合法行」值多少 —— 而这次要说清楚量的是哪一段

⚠ 我在代码注释里先写了「33 倍」，实测是 5.75 倍

一行 n 格、同行不相邻的摆法有多少个？正是斐波那契 —— n = 1..9 逐个对上（9 / 9），n = 9 时是 89 个，而 2⁹ = 512。

`n = 9` 的内层配对次数
先筛合法行	63 368
不筛（内层跑满 512）	364 544
省	★ 5.75 倍（= 512 / 89）

⚠ 而 512² / 89² ≈ 33 倍要两侧都不筛才对得上。 ⇒ ★★ 报倍数的时候必须说清楚量的是哪一段 —— 这和第 4 章 P1219、第 16 章 P1074 那几条「换尺子结论不同」是同一类，只不过这一次错的不是尺子，是范围。

★ 对照上一道 P1879：那儿这个优化一分钱都不值（12×12×4096² 本机不到一秒），这儿因为多了 j 那一维才开始值钱。

p1896Brute.cpp参照物：2^(n²) 逐格枚举（n ≤ 4，300 轮不一致 0 轮）

6度量程序和生成器

p1896Count.cpp度量程序（本页所有数字都出自它）

p1896Gen.cpp数据生成器

7一页纸


★★ 关键的一步	`f[i][j][S]` —— 多一维「已经放了几个」；上下判断从一条变三条（斜着也不行）
★ 忘了斜上方	把上一道 P1879 的转移搬来 ⇒ 超集 ⇒ 恒 ≥ 正解，被抓 147/300
★★★ 「至多 K 个」	恒 ≥ 正解，被抓 221/300；⚠ `K = 0` 那 79 轮是精确的 0（题面明写 `0 ≤ K`）
★★ `int` 够不够	搜得出来：全局最大 `n=9,K=13` 的 576 亿（int 的 26.84 倍），第一个撑破的是 `n=9,K=9`
⚠ 先筛合法行值多少	实测 5.75 倍（我先写的 33 倍要两侧都不筛）—— 报倍数要说清量的是哪一段
★ 能自己验的性质	一行的合法摆法 ≡ 斐波那契（`n = 1..9` 全对上，`n = 9` 是 89）
参照物	`2^(n²)` 逐格枚举（`n ≤ 4`）；300 轮不一致 0 轮

洛谷 P1896 互不侵犯

0题目原文（本地存了一份）

数据范围及约定

输入

输出

1★★ 和上一道 P1879 只差两处，而两处都很典型

2★★ 第一个错法：把上一道的转移原样搬过来（忘了斜上方）

3★★★ 第二个错法：「恰好 K 个」读成「至多 K 个」—— 而它有个结构性盲区

4★★★ 第三个错法：int —— 而「要不要 long long」是搜得出来的，不用猜

5★ 「先筛合法行」值多少 —— 而这次要说清楚量的是哪一段

6度量程序和生成器

7一页纸