玉米田

题目描述

$M \times N$ 的玉米田每格为 1（肥沃）或 0（贫瘠），只能在肥沃格种玉米，且相邻（上下左右）两格不能同时种。求种植方案数对 $10^8$ 取模。

思路

按行做状态压缩 DP：一行的种植状态用二进制表示，预处理出不含相邻 1 的合法状态及状态对应肥沃格掩码，再枚举相邻两行状态不冲突且都落在肥沃格内的转移，逐行累计方案数即可。

参考代码

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#!/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-10-01 02:00
# update_at: 2026-10-01 02:00

import sys

MOD = 10**8  # 题面要求的取模


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    m, n = next(data), next(data)

    # 每行的肥沃格位掩码：第 c 列肥沃则该位为 1
    fert = [sum(next(data) << c for c in range(n)) for _ in range(m)]

    # 无相邻 1 的掩码是行内种植的基础候选（s << 1 与 s 相交说明有水平相邻）
    no_adj = [s for s in range(1 << n) if s & (s << 1) == 0]

    # 每行真正可用的种植掩码：还必须是肥沃格的子集
    row_masks = [[s for s in no_adj if s & f == s] for f in fert]

    # dp：上一行种植掩码 -> 到上一行为止的方案数；第 0 行之前只有"全不种"
    dp = {0: 1}
    for masks in row_masks:
        # 上下两行不能同列种植：本行掩码 s 只能接在与其无公共位的 prev 之后
        dp = {s: sum(dp[t] for t in dp if t & s == 0) % MOD for s in masks}

    print(sum(dp.values()) % MOD)


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
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-06 01:49
 * update_at: 2026-10-06 01:49
 */

#include <cstdio>
#include <vector>
using namespace std;

typedef long long ll;

const int MAXM = 15;
const int MAXN = 15;
const int MOD = 100000000;

int m, n;
int fertile[MAXM];          // 每行肥沃格子的位掩码

ll dp[2][1 << MAXN];        // 滚动数组，dp[cur][s] 表示当前行状态为 s 的方案数

int main() {
    scanf("%d %d", &m, &n);
    for (int i = 1; i <= m; i++) {
        int mask = 0;
        for (int j = 0; j < n; j++) {
            int x;
            scanf("%d", &x);
            if (x) mask |= (1 << j);
        }
        fertile[i] = mask;
    }

    // 预处理所有无水平相邻1的掩码，同时是肥沃格子子集
    vector<int> masks[MAXM];
    int total = 1 << n;
    for (int i = 1; i <= m; i++) {
        for (int s = 0; s < total; s++) {
            if ((s & (s << 1)) == 0 && (s & fertile[i]) == s) {
                masks[i].push_back(s);
            }
        }
    }

    // 初始化：第0行之前只有状态0，方案数为1
    int cur = 0;
    dp[cur][0] = 1;

    for (int i = 1; i <= m; i++) {
        int nxt = cur ^ 1;
        // 清空下一行状态
        for (int j = 0; j < total; j++) dp[nxt][j] = 0;
        // 枚举当前行所有合法状态
        for (size_t a = 0; a < masks[i].size(); a++) {
            int s = masks[i][a];
            ll sum = 0;
            // 枚举上一行所有合法状态，要求无垂直相邻
            // 第1行的上一行是虚拟的第0行，只有状态0
            if (i == 1) {
                if ((s & 0) == 0) sum = dp[cur][0];
            } else {
                for (size_t b = 0; b < masks[i - 1].size(); b++) {
                    int t = masks[i - 1][b];
                    if ((s & t) == 0) {
                        sum += dp[cur][t];
                        if (sum >= MOD) sum -= MOD;
                    }
                }
            }
            dp[nxt][s] = sum % MOD;
        }
        cur = nxt;
    }

    ll ans = 0;
    for (int s = 0; s < total; s++) {
        ans += dp[cur][s];
        if (ans >= MOD) ans -= MOD;
    }
    printf("%lld\n", ans % MOD);
    return 0;
}

目录

题目描述

思路

参考代码