「一本通 5.4 练习 1」涂抹果酱

题目描述

$N \times M$ 网格每格染 $1/2/3$ 三色之一，要求上下左右相邻格子颜色不同。第 $K$ 行已固定，求合法染色方案数 $\bmod 10^6$ ，无解输出 $0$ 。 $1 \le N \le 10000,\ 1 \le M \le 5$ 。

样例： $N=2,\ M=2,\ K=1$ ，固定行为 $2\ 3$ ，输出 $3$ 。

思路

$M \le 5$ 时一行合法染色最多 $48$ 种，先枚举行状态并预计算相容表（上下两行逐列不同色）。把固定行第 $K$ 行拆成上下两段独立递推：上半段从全 $1$ 向量滚到第 $K-1$ 行再贴固定行；下半段从固定行单位向量滚到第 $N$ 行后求和。两段结果相乘取模即为答案。若固定行自身相邻同色则直接输出 $0$ 。

参考代码

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

import sys
from itertools import product

MOD = 10**6  # 题面要求的模数


def valid_rows(m: int) -> list[tuple[int, ...]]:
    """列出一行的所有合法涂法：M 列取 1/2/3，且相邻列颜色不同。"""
    return [
        row
        for row in product(range(1, 4), repeat=m)
        if all(row[c] != row[c + 1] for c in range(m - 1))
    ]


def build_compat(rows: list[tuple[int, ...]], m: int) -> list[list[int]]:
    """上下兼容表：compat[i] 里是与 rows[i] 上下相邻（每列颜色都不同）的行状态编号。"""
    return [
        [j for j, nxt in enumerate(rows) if all(row[c] != nxt[c] for c in range(m))]
        for row in rows
    ]


def propagate(vec: list[int], compat: list[list[int]], steps: int) -> list[int]:
    """行状态计数向量向下推 steps 行：每个状态累加所有能接在它上面的状态。"""
    for _ in range(steps):
        vec = [sum(map(vec.__getitem__, js)) % MOD for js in compat]
    return vec


def count_plans(n: int, m: int, k: int, fixed: tuple[int, ...]) -> int:
    """第 K 行固定时的合法涂法数：固定行上、下两侧分别做行状态 DP 再相乘。"""
    rows = valid_rows(m)
    if fixed not in rows:  # 固定行自己相邻同色，任何延伸都不合法
        return 0
    compat = build_compat(rows, m)
    me = rows.index(fixed)
    touch = compat[me]  # 兼容表对称：能紧贴固定行上/下的行状态

    # 上半段：第 1 行任取合法状态，推到第 K-1 行，再要求它贴住固定行；K=1 时上方为空
    up = 1
    if k > 1:
        vec = propagate([1] * len(rows), compat, k - 2)  # K-1 行共 K-2 次转移
        up = sum(vec[p] for p in touch) % MOD

    # 下半段：从固定行出发推到第 N 行，末行无约束，全部状态求和
    down = 1
    if k < n:
        vec = [1 if i == me else 0 for i in range(len(rows))]
        down = sum(propagate(vec, compat, n - k)) % MOD

    return up * down % MOD


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m, k = next(data), next(data), next(data)
    fixed = tuple(next(data) for _ in range(m))
    print(count_plans(n, m, k, fixed))


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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132/**
 * 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 00:54
 * update_at: 2026-10-06 00:54
 */

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

typedef long long ll;

const int MOD = 1000000;

int n, m, K;
int fixed_row[6]; // 第 K 行的固定颜色，下标 1..m

// 一行的合法状态：用 1/2/3 表示颜色，相邻列不同
vector<vector<int>> rows; // rows[i][c] 第 i 个状态第 c 列的颜色

// compat[i] 表示能与 rows[i] 上下相邻的状态编号列表（逐列颜色都不同）
vector<vector<int>> compat;

// 生成所有合法行状态
void gen_rows(int dep) {
    static int cur[6];
    if (dep > m) {
        vector<int> tmp(m + 1);
        for (int c = 1; c <= m; ++c) tmp[c] = cur[c];
        rows.push_back(tmp);
        return;
    }
    for (int color = 1; color <= 3; ++color) {
        if (dep > 1 && color == cur[dep - 1]) continue; // 与左邻同色则跳过
        cur[dep] = color;
        gen_rows(dep + 1);
    }
}

// 建相容表
void build_compat() {
    int S = rows.size();
    compat.assign(S, vector<int>());
    for (int i = 0; i < S; ++i) {
        for (int j = 0; j < S; ++j) {
            bool ok = true;
            for (int c = 1; c <= m; ++c) {
                if (rows[i][c] == rows[j][c]) {
                    ok = false;
                    break;
                }
            }
            if (ok) compat[i].push_back(j);
        }
    }
}

// 行状态计数向量向下推 steps 行
vector<int> propagate(vector<int> vec, int steps) {
    int S = rows.size();
    for (int step = 0; step < steps; ++step) {
        vector<int> nxt(S, 0);
        for (int j = 0; j < S; ++j) {
            ll sum = 0;
            for (int idx = 0; idx < (int)compat[j].size(); ++idx) {
                sum += vec[compat[j][idx]];
            }
            nxt[j] = (int)(sum % MOD);
        }
        vec.swap(nxt);
    }
    return vec;
}

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

    cin >> n >> m >> K;
    for (int c = 1; c <= m; ++c) cin >> fixed_row[c];

    gen_rows(1);
    build_compat();

    // 查找固定行对应的状态编号
    int me = -1;
    for (int i = 0; i < (int)rows.size(); ++i) {
        bool same = true;
        for (int c = 1; c <= m; ++c) {
            if (rows[i][c] != fixed_row[c]) {
                same = false;
                break;
            }
        }
        if (same) {
            me = i;
            break;
        }
    }
    if (me == -1) { // 固定行自身相邻同色，不存在合法方案
        cout << 0 << "\n";
        return 0;
    }

    // 上半段：第 1 行任取合法状态，推到第 K-1 行，再要求贴住固定行
    int up = 1;
    if (K > 1) {
        vector<int> vec(rows.size(), 1); // 第一行每个合法状态各 1 种
        vec = propagate(vec, K - 2);     // 推到第 K-1 行
        ll sum = 0;
        for (int idx = 0; idx < (int)compat[me].size(); ++idx) {
            sum += vec[compat[me][idx]];
        }
        up = (int)(sum % MOD);
    }

    // 下半段：从固定行出发推到第 N 行，末行无约束全部求和
    int down = 1;
    if (K < n) {
        vector<int> vec(rows.size(), 0);
        vec[me] = 1; // 固定行状态为 1
        vec = propagate(vec, n - K);
        ll sum = 0;
        for (int i = 0; i < (int)vec.size(); ++i) sum += vec[i];
        down = (int)(sum % MOD);
    }

    cout << (ll)up * down % MOD << "\n";
    return 0;
}

「一本通 5.4 练习 1」涂抹果酱

目录

题目描述

思路

参考代码