信息学奥赛算法练功房◌检测中
题单　·　习题解析

洛谷 P1879 Corn Fields

棋盘状压入门：⚠⚠ 「漏掉全荒废」这个名字就起错了 —— 它减掉的是 f[m][0] 一整类方案（≡ 300/300）；★★★ 模数写成 1e9+7 在 4×4/6×6 上是结构性的 0

原题：洛谷 P1879出自 第 28 章 状压 DP 入门：旅行商问题 的题单题面本地存档：2026-08-30
⚠ 先自己写一遍，再往下看

这一页不是标准答案，是一条阶梯：把大多数人真实会写出的第一版摆出来， 看它错在哪、慢在哪，再一步一步改。所以它对「已经自己动手撞过一次墙」的人最有用。
还没写过的话，先去写 —— 写出来的哪怕是错的，也比直接看这一页收获大。

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

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

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

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

题目描述

农场主 John 新买了一块长方形的新牧场，这块牧场被划分成 M 行 N 列 (1 ≤ M ≤ 12, 1 ≤ N ≤ 12)， 每一格都是一块正方形的土地。John 打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。

遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉， 于是 John 不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。

John 想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？ （当然，把新牧场完全荒废也是一种方案）

输入格式

第一行：两个整数 M 和 N，用空格隔开。

第 2 到第 M+1 行：每行包含 N 个用空格隔开的整数，描述了每块土地的状态。 第 i+1 行描述了第 i 行的土地，所有整数均为 0 或 1， 是 1 的话，表示这块土地足够肥沃，0 则表示这块土地不适合种草。

输出格式

一个整数，即牧场分配总方案数除以 10⁸ 的余数。

输入输出样例

输入

2 3
1 1 1
0 1 0

输出

9

2 × 3 的牧场，第二行只有中间那格是肥沃的。九种方案 ⇒ 9。

⚠ 这一组样例只挡住了三个错法里的两个（漏掉 S = 0 那一格打出 4、忘判同行相邻打出 12）—— 而「模数写成 10⁹+7」原样打出 9，⚠ 它在这个规模上根本不可能被抓到（见第 ④ 步）。

1★★ 状压 DP 的另一大类：压的不是「去过哪些点」，是「这一行怎么摆」

★ 一行 N 格 ⇒ 一个 N 位二进制数就是一整行的方案

同题单的 P1171 压的是「已经去过哪些城市」；这道题压的是一行的选法。

    f[i][S] = 前 i 行都摆好了、且第 i 行的选法恰好是 S 时的方案数
    f[i][S] = Σ f[i-1][T]        要求 (S & T) == 0

三条约束，每条都是一行位运算：

约束 怎么写
① 同一行内不能左右相邻 (S & (S << 1)) == 0
② 不能种在贫瘠的地上 (S & ~good[i]) == 0
③ 上下两行不能相邻 (S & T) == 0

★ 第 0 行想象成一整行空地（f[0][0] = 1），这样第 1 行就不用特判了 —— 和第 27 章那个「超级源点」是同一个手法：造一个虚拟的边界，把特判消掉。

p1879.cpp★ 这一版就能 AC
// P1879 Corn Fields —— 正解：**按行**状压 DP，O(m × 2ⁿ × 2ⁿ)
//
// ★ 这是状压 DP 的**另一大类**：[P1171](/sol/p1171/) 那种压的是「去过哪些点」，
//   这一类压的是「**这一行的选法**」——
//   一行 n 格，每格种/不种 ⇒ 一个 n 位二进制数就是一整行的方案。
//
//   f[i][S] = 前 i 行都摆好了、且第 i 行的选法恰好是 S 时的方案数
//   f[i][S] = Σ f[i-1][T]      要求 (S & T) == 0
//
// 三个判断全是位运算，各一行：
//   ① 同一行内不能相邻      (S & (S << 1)) == 0
//   ② 不能种在贫瘠的地上    (S & ~good[i]) == 0    ⇔  (S | good[i]) == good[i]
//   ③ 上下两行不能相邻      (S & T) == 0
//
// ⚠ 题面要求对 **10⁸** 取模（不是常见的 1e9+7）——**照抄题面，别用肌肉记忆**。
// ⚠ 「把新牧场完全荒废也是一种方案」⇒ S = 0 是合法的，答案里必须算上它。


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


const int MOD = 100000000;      // ← 题面写的就是 10⁸


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


    int m, n;
    if (!(cin >> m >> n)) return 0;
    vector<int> good(m + 1, 0);
    for (int i = 1; i <= m; i++)
        for (int j = 0; j < n; j++) {
            int v;
            cin >> v;
            if (v) good[i] |= 1 << j;              // 1 = 肥沃，可以种
        }


    int full = 1 << n;
    vector<vector<long long>> f(m + 1, vector<long long>(full, 0));
    // 第 0 行想象成一整行空地：只有「什么都没种」这一种状态
    f[0][0] = 1;


    for (int i = 1; i <= m; i++)
        for (int S = 0; S < full; S++) {
            if (S & (S << 1)) continue;            // ① 同行相邻
            if (S & ~good[i]) continue;            // ② 种到了贫瘠地上
            for (int T = 0; T < full; T++) {
                if (S & T) continue;               // ③ 和上一行竖着挨着
                f[i][S] = (f[i][S] + f[i - 1][T]) % MOD;
            }
        }


    long long ans = 0;
    for (int S = 0; S < full; S++) ans = (ans + f[m][S]) % MOD;
    cout << ans << '\n';
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果

2★ 第一个错法：忘了判「同一行内左右相邻」

p1879NoRow.cpp✗ 少了 S & (S << 1) 那一句
// ✗ P1879：忘了判「同一行内左右相邻」
//
// 三条约束里最容易漏的一条 —— 因为「上下不相邻」写在转移里很显眼（S & T），
// 而「左右不相邻」是行内的事，得单独写一句 `S & (S << 1)`。
// ★ 它少了一条限制 ⇒ 它数的方案**是正解的超集** ⇒ 答案**恒 ≥ 正解**（模之前）。


#include <bits/stdc++.h>
using namespace std;
const int MOD = 100000000;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n;
    if (!(cin >> m >> n)) return 0;
    vector<int> good(m + 1, 0);
    for (int i = 1; i <= m; i++)
        for (int j = 0; j < n; j++) { int v; cin >> v; if (v) good[i] |= 1 << j; }
    int full = 1 << n;
    vector<vector<long long>> f(m + 1, vector<long long>(full, 0));
    f[0][0] = 1;
    for (int i = 1; i <= m; i++)
        for (int S = 0; S < full; S++) {
            if (S & ~good[i]) continue;                  // ← 少了 S & (S << 1) 那一句
            for (int T = 0; T < full; T++) {
                if (S & T) continue;
                f[i][S] = (f[i][S] + f[i - 1][T]) % MOD;
            }
        }
    long long ans = 0;
    for (int S = 0; S < full; S++) ans = (ans + f[m][S]) % MOD;
    cout << ans << '\n';
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果

三条约束里最容易漏的一条 —— 因为「上下不相邻」写在转移里很显眼（S & T）， 而「左右不相邻」是行内的事，得单独写一句。

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

3⚠⚠ 第二个错法：我给它起的名字就是错的

题面特意补了一句「（当然，把新牧场完全荒废也是一种方案）」。 看到这句话很自然会想：「那我把 S = 0 那一格排除掉，看看会怎样」。

p1879NoEmpty.cpp✗ 求和时从 S = 1 开始
// ✗ P1879：漏掉了「什么都不种」这种方案
//
// 题面特意补了一句「（当然，把新牧场完全荒废也是一种方案）」，于是很自然会想到
// 「那我把 S = 0 那一格排除掉试试」。
//
// ⚠⚠ 草稿里我写的是「它把答案减了 1」。**实测当场打脸**：官方样例上正解 9、它给 4，差的是 5。
//    真相是 `f[m][0]` **不是 1**，它是「**最后一行什么都不种**」的方案数（前面几行随便摆）。
//
// ★★★ 说清楚之后就成了一条等式：它**恒等于「正解 − f[m][0]」**，
//    也就是**「最后一行至少种了一棵」的方案数** —— 300 / 300 轮一个不差。
//    ⇒ 「漏掉全荒废那一种」这个说法本身就是错的，它漏掉的是一整类方案。


#include <bits/stdc++.h>
using namespace std;
const int MOD = 100000000;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n;
    if (!(cin >> m >> n)) return 0;
    vector<int> good(m + 1, 0);
    for (int i = 1; i <= m; i++)
        for (int j = 0; j < n; j++) { int v; cin >> v; if (v) good[i] |= 1 << j; }
    int full = 1 << n;
    vector<vector<long long>> f(m + 1, vector<long long>(full, 0));
    f[0][0] = 1;
    for (int i = 1; i <= m; i++)
        for (int S = 0; S < full; S++) {
            if (S & (S << 1)) continue;
            if (S & ~good[i]) continue;
            for (int T = 0; T < full; T++) {
                if (S & T) continue;
                f[i][S] = (f[i][S] + f[i - 1][T]) % MOD;
            }
        }
    long long ans = 0;
    for (int S = 1; S < full; S++) ans = (ans + f[m][S]) % MOD;   // ← 从 1 开始，漏了 S = 0
    cout << ans << '\n';
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
★★★ 草稿说「它把答案减了 1」——官方样例当场打脸：9 → 4，差的是 5

真相是 f[m][0] 根本不是 1：它是「最后一行什么都不种」的方案数 （前面几行可以随便摆）。样例里那是 5 种。

★★★ 说清楚之后就成了一条精确的等式：
它被抓 300 / 300
它 ≡ 正解 − f[m][0]（= 「最后一行至少种了一棵」的方案数） ★ 300 / 300，一个不差

⇒ ★★ 所以「漏掉全荒废那一种」这个说法本身就是错的 —— 它漏掉的是一整类方案。 这又一次印证第 14 章 P1332 立的那条： 说清楚一个 bug「算了什么」，比说它「错了」有用得多 —— 名字起对了，等式和抓获率都是白送的。

4★★★ 第三个错法：模数写成 10⁹+7 —— 而它在小数据上是结构性的 0

p1879Mod7.cpp✗ 模数用了肌肉记忆里的那个
// ✗ P1879：模数写成了 10⁹+7（肌肉记忆）
//
// ★ 题面白纸黑字写着「除以 10⁸ 的余数」。10⁹+7 是竞赛里最常见的模数，
//   手指头会自己打出来 —— 而这道题不是。
// ⇒ 被抓的轮数 ≡ **真实方案数越过 10⁸** 的轮数（那条线是能算出来的，见 Count 第 ④ 段）。


#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;     // ← 这里
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n;
    if (!(cin >> m >> n)) return 0;
    vector<int> good(m + 1, 0);
    for (int i = 1; i <= m; i++)
        for (int j = 0; j < n; j++) { int v; cin >> v; if (v) good[i] |= 1 << j; }
    int full = 1 << n;
    vector<vector<long long>> f(m + 1, vector<long long>(full, 0));
    f[0][0] = 1;
    for (int i = 1; i <= m; i++)
        for (int S = 0; S < full; S++) {
            if (S & (S << 1)) continue;
            if (S & ~good[i]) continue;
            for (int T = 0; T < full; T++) {
                if (S & T) continue;
                f[i][S] = (f[i][S] + f[i - 1][T]) % MOD;
            }
        }
    long long ans = 0;
    for (int S = 0; S < full; S++) ans = (ans + f[m][S]) % MOD;
    cout << ans << '\n';
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果

题面白纸黑字写着「除以 10⁸ 的余数」。而 10⁹+7 是竞赛里最常见的模数，手指头会自己打出来。

★★★ 被抓轮数 ≡ 真实方案数越过 10⁸ 的轮数 —— 而规模这把旋钮决定一切
档位（各 60 轮） 被抓 真实方案数 ≥ 10⁸ 的轮数
4 × 4，肥沃率 70% ★ 0 ★ 0
6 × 6，肥沃率 70% ★ 0 ★ 0
12 × 12，肥沃率 70% 60 60
12 × 12 全肥沃 60 60

四档全都一个不差。 ⇒ 这个 bug 的触发条件就是一句话：方案数得先超过 10⁸。

⚠⚠ 而这意味着：顺手写个 4 × 4 的生成器跑一万轮，也永远抓不到它 —— 这是第 21 章 P1077 那条「抓不到它的是档位，不是轮数」的又一次现场 （那道题的模数 bug 也是同一个形状）。 ⇒ ★★ 生成器的规模必须照着题面顶格来，而不是「小一点好对拍」。

5★ 三条约束各自值多少 ＋ 一个能顺手省 10.9 倍的地方

12 × 12 全肥沃
真实方案数 约 1.6 × 10²⁶ ⇒ ★ 早就超出 unsigned long long，所以题目才要取模
撤掉「同行不相邻」之后 约 8.2 × 10³⁰（涨 5 万倍）
一行的合法选法（同行不相邻）有几个 ★ 377 个（正是斐波那契 F(14)）
而 2¹² = 4096
★★ 那个 377 是可以拿来提速的

内层枚举 T 那一层跑满了 2¹² = 4096，可其中只有 377 个是合法行 —— 浪费了 10.9 倍。把合法行先筛出来存成一张表再两两配对，是这类题的标准优化。

⚠ 但在这道题上它一分钱都不值：12 × 12 × 4096 × 4096 ≈ 2.4 × 10⁸，本机不到一秒。 ⇒ 又一次「一个优化值多少倍，主语是数据和规模」—— 它真正值钱是在下一道 P1896（还要多一维「已经放了几个」）上。

p1879Brute.cpp参照物：2^(M×N) 逐格枚举（300 轮不一致 0 轮）

6度量程序和生成器

p1879Count.cpp度量程序（本页所有数字都出自它）
p1879Gen.cpp数据生成器

7一页纸
★★ 关键的一步 压的是一行的选法；三条约束各一行位运算；f[0][0] = 1 造个虚拟空行消掉特判
★ 忘判同行相邻 少一条限制 ⇒ 超集 ⇒ 恒 ≥ 正解，被抓 299/300（样例挡住）
⚠⚠ 「漏掉全荒废」 名字就起错了：它减掉的是 f[m][0]（最后一行全空的一整类方案）—— ≡ 300/300
★★★ 模数写成 10⁹+7 被抓轮数 ≡ 方案数越过 10⁸ 的轮数（四档全对上）；⚠ 4×4/6×6 是结构性的 0
★ 顺手能省的 合法行只有 377 个而 2¹² = 4096 ⇒ 内层浪费 10.9 倍（⚠ 这道题上不值，下一道值）
参照物 2^(M×N) 逐格枚举；300 轮不一致 0 轮
规模 12×12 全肥沃真实方案数约 1.6 × 10²⁶ ⇒ 超 unsigned long long，所以要取模