形式化题目

给定 $M$ 行 $N$ 列的 0/1 网格（$1 \leqslant M, N \leqslant 12$），值为 $1$ 的格子称为肥沃格，值为 $0$ 的格子贫瘠、不可使用。求满足下列两个条件的格子集合个数：

1. 集合只由肥沃格组成；
2. 集合中任意两格不共享公共边（上下或左右相邻）。

空集合（一格不种）也计入答案，输出答案对 $10^8$ 取模的结果。

这就是网格图上的独立集计数：有边当且仅当两格四相邻，贫瘠格等价于"必须不选"的顶点。

样例网格（$M = 2$、$N = 3$）与它的掩码编码如下。把每行的选择压成 $N$ 位二进制，低位对应左侧第 0 列：

表中"合法掩码"须同时满足两点：不含横向相邻的两个 1（如 011、110 被排除），且只踩肥沃格（第 1 行的 001、100 落在贫瘠格上被排除）。样例答案为 $9$，推演见下文。

正解

思路

朴素做法与瓶颈。 最直接的想法是枚举全部 $2^{MN}$ 个格子子集，再逐对检查是否相邻：$MN$ 最大 $144$，$2^{144}$ 完全不可行；改成"逐格选/不选 + 与已选格相邻则剪枝"的回溯，最坏复杂度仍是指数级。瓶颈在于它把 144 个格子当成互相关联的维度——但相邻关系只发生在同一行内和上下两行之间，与更远的行毫无关系，状态里根本不必记住那么久的历史。

观察一：按行推进，把一行压成一个掩码。 先决定第 0 行种哪些格，再决定第 1 行……第 $M-1$ 行。第 $r$ 行的选择压成 $N$ 位掩码 $s$（第 $c$ 位为 1 表示格 $(r, c)$ 种草）：

• 横向冲突只在掩码内部：$s$ 合法 $\iff$ s & (s << 1) == 0，即没有两个横向相邻的 1；
• 贫瘠格只在本行过滤：设 fertile[r] 为第 $r$ 行肥沃格掩码，则要求 s & ~fertile[r] == 0。

$N \leqslant 12$，无相邻 1 的掩码只有 377 个（$N = 12$ 时，计数恰为斐波那契数 $F_{N+2}$），远小于 $2^{12} = 4096$。

观察二：跨行约束只是两掩码相容。 相邻两行只有"同列同时种草"才会纵向相邻，因此第 $r-1$ 行掩码 $t$ 与第 $r$ 行掩码 $s$ 相容 $\iff$ t & s == 0。三个条件（横向、纵向、贫瘠格）各由一条位运算负责，无需任何几何检查。

状态与转移。 逐行滚动，记

其中 $s$ 自身须无横向相邻且只踩肥沃格，则对 $r \geqslant 1$

初始时把第 0 行上方视为空行：$dp = \{0 \mapsto 1\}$（空掩码唯一且合法），第 0 行的转移用同一个式子、把空掩码当作 $t$；处理完第 $M-1$ 行后，所有掩码的方案数求和即为答案——这自然包含了"最后一行不种"乃至全程空方案。每步累加后对 $10^8$ 取模。

样例推演。 样例的逐行 DP 转移表（掩码写成三位二进制）：

读表可以看到转移的两个方向：000 $\mapsto$ 5 是"第 1 行一格不种"，上一行怎么种都行；010 $\mapsto$ 4 中上一行的 010 因纵向同列被排除，其余 4 个都可接。合计 $9$，与样例输出一致。

正确性。 对行数归纳：任一合法方案在每行的掩码必然满足"掩码合法 + 只踩肥沃格 + 与上一行按位与为 0"，其贡献恰在对应转移中被累加一次（不漏）；而方案由各行掩码唯一确定，不同转移路径对应不同方案（不重）。初始与求和边界把"全程不种"和"末行不种"都计入，故总和即所求。

实现对应。 main.py 中，valid 用一个列表推导一次性筛出无横向相邻的掩码（与行无关）；每行的 row_ok 再按 fertile[r] 剔除踩贫瘠格的掩码；双层循环 for prev, cnt in dp.items(): for s in row_ok: if not s & prev: 就是转移式，nxt[s] = (nxt.get(s, 0) + cnt) % MOD 完成求和与取模；dp = nxt 滚动到下一行，最后 sum(dp.values()) % MOD 输出。

代码

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#!/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:39
# update_at: 2026-09-30 20:39

import sys

MOD = 10**8  # 题面要求输出方案数除以 10^8 的余数


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    m, n = next(data), next(data)  # m 行 n 列
    cells = [next(data) for _ in range(m * n)]  # 行优先铺开的全部格子

    # 每行压成 n 位掩码：第 c 位为 1 表示该格肥沃可种草
    fertile = [
        sum(1 << c for c in range(n) if cells[r * n + c])  # 行内逐格置位
        for r in range(m)
    ]

    # 与肥沃度无关的公共候选：n 位内没有横向相邻 1 的掩码（含空掩码 0）
    valid = [s for s in range(1 << n) if not s & (s << 1)]

    dp = {0: 1}  # 逐行推进：上一行的种植掩码 -> 方案数；第 0 行上方视为空行
    for r in range(m):
        row_ok = [s for s in valid if not s & ~fertile[r]]  # 剔除落在贫瘠格上的掩码
        nxt: dict[int, int] = {}
        for prev, cnt in dp.items():
            for s in row_ok:
                if not s & prev:  # 与上一行同列不同时种草，杜绝纵向相邻
                    nxt[s] = (nxt.get(s, 0) + cnt) % MOD
        dp = nxt

    print(sum(dp.values()) % MOD)  # 末行任意掩码都合法，求和即总方案数


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
84/**
 * 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:23
 * update_at: 2026-10-05 11:23
 */
// main.cpp：按行状压 DP，统计网格上不相邻种草方案数。
#include <cstdio>

typedef long long ll;

const int MAXN = 13;
const ll MOD = 100000000; // 题面要求方案数对 10^8 取模

int m, n;
int fertile[MAXN];            // fertile[r]：第 r 行肥沃格掩码，第 c 位为 1 表示可种草
int valid_mask[1 << MAXN];    // 所有不含横向相邻 1 的掩码
int valid_cnt;

ll dp[1 << MAXN];   // dp[s]：处理到上一行、且上一行种植掩码恰为 s 的方案数
ll nxt[1 << MAXN];  // nxt[s]：处理到本行、且本行种植掩码恰为 s 的方案数

int main() {
    scanf("%d%d", &m, &n);
    for (int r = 0; r < m; r++) {
        int mask = 0;
        for (int c = 0; c < n; c++) {
            int x;
            scanf("%d", &x);
            if (x == 1) {
                mask |= 1 << c; // 第 c 位为 1 表示这一格肥沃
            }
        }
        fertile[r] = mask;
    }

    // 与行无关的公共候选：掩码内部没有两个相邻的 1
    valid_cnt = 0;
    for (int s = 0; s < (1 << n); s++) {
        if ((s & (s << 1)) == 0) {
            valid_mask[valid_cnt] = s;
            valid_cnt++;
        }
    }

    // 初始时把第 0 行上方视为空行，只有空掩码 1 种方案
    for (int s = 0; s < (1 << n); s++) {
        dp[s] = 0;
    }
    dp[0] = 1;

    for (int r = 0; r < m; r++) {
        for (int s = 0; s < (1 << n); s++) {
            nxt[s] = 0;
        }
        for (int i = 0; i < valid_cnt; i++) {
            int s = valid_mask[i];
            if (s & ~fertile[r]) {
                continue; // 该掩码踩到了贫瘠格
            }
            ll sum = 0;
            for (int j = 0; j < valid_cnt; j++) {
                int t = valid_mask[j];
                if (s & t) {
                    continue; // 与上一行同列同时种草，会产生纵向相邻
                }
                sum += dp[t];
            }
            nxt[s] = sum % MOD;
        }
        for (int s = 0; s < (1 << n); s++) {
            dp[s] = nxt[s]; // 滚动到下一行
        }
    }

    // 末行任意合法掩码都可以作为结尾，求和即总方案数（含全程不种）
    ll ans = 0;
    for (int s = 0; s < (1 << n); s++) {
        ans = (ans + dp[s]) % MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

复杂度

• 时间：预筛合法掩码 $O(2^N)$；每行过滤 $O(|V|)$、转移 $O(|V|^2)$，总计 $O(2^N + M \cdot |V|^2)$，其中 $|V| \leqslant 377$。最坏约 $12 \times 377^2 \approx 1.7 \times 10^6$ 次字典操作，与 C++ 正解同阶；实测 10 组真实数据单例耗时约 $0.02$ s（OJ 限时 1000 ms）。
• 空间：valid、row_ok、dp、nxt 均为 $O(|V|) = O(2^N)$，上限 377 个字典项，实测峰值约 $15$ MB（限制 128 MB）。

总结

• 相邻约束是局部的：行内只看本行掩码，行间只看上下两行掩码。按行推进 + 位掩码状态，把 $2^{144}$ 的子集枚举压缩成 $M$ 层、每层至多 377 个状态的滚动 DP。
• 三条约束各对应一条位运算：横向不相邻 s & (s << 1) == 0、不踩贫瘠格 s & ~fertile[r] == 0、纵向不相邻 t & s == 0。掩码是"把一行几何冲突翻译成代数条件"的工具。
• 计数 DP 的两个易错点：初始状态要包含空掩码（否则丢掉不种的方案），结束时要对所有掩码求和而非只取某个状态；模数是 $10^8$ 而非常见的 $10^9+7$，每次累加后都要取模。