usaco-6.1.1 邮政货车

形式化题目

郊区由 4 条东西向街道与 N 条南北向街道正交组成，相邻街道的交叉口共有 $4N$ 个。把交叉口记作 $(r, c)$ ，其中行 $r \in \{0,1,2,3\}$ 自北向南、列 $c \in \{0, 1, \dots, N-1\}$ 自西向东编号，邮局位于西北角 $(0, 0)$ 。

要求数出满足下列条件的行驶路线条数：从 $(0,0)$ 出发，每个交叉口恰好经过一次，最后回到 $(0,0)$ 。

两条路线只要边的使用顺序不同就算不同，因此沿同一条闭合回路顺时针走与逆时针走算两条。

$N = 4$ 时答案是 12。下图画出 $N = 3$ 与 $N = 4$ 的全部走法（@ 是邮局，o 是其他交叉口，- / | 是被走过的街道）。

$N = 3$ 的 2 种走法（每种正反两个方向，共 4 条路线）：

text

1
2
3
4
5
6
7@- o- o    @- o- o
|   |      |   |
o  o- o    o- o  o
| |          | |
o  o- o    o- o  o
|   |      |   |
o- o- o    o- o- o

$N = 4$ 的 6 种走法（每种正反两个方向，共 12 条路线）：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15@- o- o- o    @- o  o- o    @- o  o- o
|     |       | | | |       | | | |
o  o- o  o    o  o- o  o    o  o  o  o
| | | |       |     |       | | | |
o  o  o  o    o  o- o  o    o  o- o  o
| | | |       | | | |       |     |
o- o  o- o    o- o  o- o    o- o- o- o

@- o- o- o    @- o- o- o    @- o- o- o
|     |       |     |       |     |
o  o- o- o    o- o  o- o    o- o- o  o
| |             | |             | |
o  o- o- o    o- o  o- o    o- o- o  o
|     |       |     |       |     |
o- o- o- o    o- o- o- o    o- o- o- o

观察要点：每条路线在网格里都是一个闭合的圈，每个交叉口恰好用掉两条街道。这正是图论里的哈密顿回路；把起点固定在 $(0,0)$ 后，回路数与路线数只差一个因子 2。

正解

思路

建模：从「走法」到「选边」

要求「每个交叉口恰好经过一次」，等价于在每个交叉口上恰好用掉两条街道：一条进、一条出（无向意义下就是选中两条相邻的街道）。于是问题变成：

在 $4 \times N$ 网格图的边集中选出一个子集，使每个顶点的度数恰好为 2，且选出的边恰好构成一个环。

「度数全为 2」是纯局部条件，逐列处理时只需检查当前列；而「只有一个环」这个连通性条件，可以通过记住「切口上哪些端点属于同一条未完成的路径」来追踪。

关键观察：竖边不跨列，切口上只有配对信息

所有南北向街道都只在同一列内连接相邻两行，所以扫描可以一列一列地进行。处理第 $c$ 列时只涉及三种边：左侧横边（上一列已定）、本列竖边、右侧横边。

每个顶点的度数恒为 2，因此在第 $c$ 列与第 $c+1$ 列之间的切口上，需要记住的信息就是：跨过切口的横边如何两两配对（同一条未完成的路径的两端在同一组）。4 行之间可达的配对方式只有 7 种：

\varnothing,\quad \{01\},\quad \{03\},\quad \{12\},\quad \{23\},\quad \{01,23\},\quad \{03,12\}.

花括号里的数字表示配在一起的两行，例如 $\{03\}$ 表示第 0 行与第 3 行的横边由同一条路径连着。

一列的合法性判定

固定旧切面后，枚举本列的竖边子集（ $2^3 = 8$ 种）与向右横边子集（ $2^4 = 16$ 种），用「每个交叉口度数 = 2」筛掉非法组合。对剩下的组合，把旧路径、本列竖边与新横边按连通性合并：

一个连通块恰好有两个朝右端口 → 给出新切面的一组配对；
一个连通块两个端口都朝左 → 闭环了，此时若还有别的连通块、或右侧仍伸着横边，则整列不合法。

由此得到转移表（行 = 旧切面，中间几列 = 新切面，末列 = 本列收口的方案数）：

旧切面	$\{03\}$	$\{01,23\}$	$\{01\}$	$\{23\}$	$\{12\}$	$\{03,12\}$	收口
$\varnothing$	1	1
$\{01\}$	1	1
$\{23\}$	1	1
$\{01,23\}$	1	1
$\{12\}$	1
$\{03\}$			1	1	1	1	1
$\{03,12\}$			1	1		1	1

表格读法：从 $\{03\}$ 出发有 4 种方式转移到 $\{01\}$ 、 $\{12\}$ 、 $\{23\}$ 、 $\{03,12\}$ ，另有 1 种方式在本列直接收口。逐列统计（ $n = 6$ 的中间过程）：

已扫过列数	$\varnothing$	$\{01\}$	$\{03\}$	$\{12\}$	$\{23\}$	$\{01,23\}$	$\{03,12\}$	本列收口
1	1	0	0	0	0	0	0	0
2	0	0	1	0	0	1	0	0
3	0	1	1	1	1	1	1	0
4	0	2	4	1	2	3	2	0
5	0	6	8	4	6	7	6	0
6	0	14	23	8	14	19	14	37

第 1 列左侧没有横边，只有空切面一种状态；扫描到第 6 列时收口 37 次，乘以方向因子 2 恰好是 $N = 6$ 的答案 74。

为什么可以只做 $O(N)$ 次转移

第一列左侧的空切面是唯一的初始状态，前两个转移结果固定：

第 1 列之后： $\{03\}$ 与 $\{01,23\}$ 各 1；
第 2 列之后： $\{01\}$ 、 $\{03\}$ 、 $\{12\}$ 、 $\{23\}$ 、 $\{01,23\}$ 、 $\{03,12\}$ 各 1。

此后每往右一列乘一次上面的转移矩阵，共 $N-1$ 次；矩阵维数固定为 7，所以整体时间是 $O(N)$ ，额外空间 $O(1)$ 。第 $N$ 列右侧没有横边，只能收口，答案就是「第 $N$ 列收口数 $\times 2$ 」。

main.py 把这个矩阵按列写成 7 个变量的一次元组赋值，与上面的转移表逐列对应。

代码

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

import sys

# 路线 = 走遍 4×N 个路口、回到邮局的闭合走法，即 4×N 网格上的哈密顿回路。
# 南北向街道只在同一列内连接相邻两行，所以可以从西往东一列一列地决定用哪些边；
# 每个路口度数恰好为 2，于是扫到某条列间切口时只需记住"跨过切口的横边两两配成一组"
# 这一件事，而 4 行之间只有 7 种配得出来的切面：
#
#   ∅、{01}、{03}、{12}、{23}、{01,23}、{03,12}      （数字 = 配对的两行）
#
# 下表是"扫过一列"的转移（行=旧切面，列=新切面，末列=本列收口数）。
#
#           | {03} {01,23} | {01} {23} {12} {03,12} | 收口
#   ∅       |  1     1     |                         |
#   {01}    |  1     1     |                         |
#   {23}    |  1     1     |                         |
#   {01,23} |  1     1     |                         |
#   {12}    |  1           |                         |
#   {03}    |              |  1    1    1    1       |  1
#   {03,12} |              |  1    1         1       |  1


def count_routes(n: int) -> int:
    """4×n 网格上从左上角出发、每个路口恰好经过一次的闭合路线条数。"""
    # 邮局左边的切口：还没有横边跨过来，只有空切面
    empty, s01, s03, s12, s23, s01_23, s03_12 = 1, 0, 0, 0, 0, 0, 0
    for _ in range(n - 1):        # 扫过第 1 … n-1 列；第 n 列右侧没有横边，只能收口
        # 右端全部取旧值；每一行对应上表的一列
        empty, s01, s03, s12, s23, s01_23, s03_12 = (
            0,                                        # 空切面只在第一列左侧存在
            s03 + s03_12,                             # 新 {01}
            empty + s01 + s12 + s23 + s01_23,         # 新 {03}
            s03,                                      # 新 {12}
            s03 + s03_12,                             # 新 {23}
            empty + s01 + s23 + s01_23,               # 新 {01,23}
            s03 + s03_12,                             # 新 {03,12}
        )
    return 2 * (s03 + s03_12)     # 收口处的一条回路，顺时针与逆时针是两条路线


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


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/**
 * 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 13:15
 * update_at: 2026-10-06 13:15
 */

// 4×N 网格上的哈密顿回路计数：按列扫描，切口上横边的配对方式只有 7 种，
// 逐列做一次固定的线性转移；N=1000 时答案约 340 位，用压位高精度加法维护。
#include <cstdio>

typedef long long ll;

const ll BASE = 1000000000LL; // 大数按 10^9 压位，每个数组元素存 9 位十进制
const int MAXL = 55;          // N=1000 时答案约 340 位（39 段），多留空间给进位

// 状态编号（切口上配在一起的两行）：
// 0: 空切面   1:{01}   2:{03}   3:{12}   4:{23}   5:{01,23}   6:{03,12}
ll big[7][MAXL];
int len[7]; // big[s] 当前的段数

ll tmp[7][MAXL];
int tlen[7]; // 下一列的转移结果，算完再拷回 big，避免边加边覆盖

// tmp[dst] += big[src]（把旧列的状态加进新列的某个状态）
void add_old(int dst, int src) {
    if (len[src] > tlen[dst]) tlen[dst] = len[src];
    for (int i = 0; i < len[src]; i++) {
        tmp[dst][i] += big[src][i];
        if (tmp[dst][i] >= BASE) { // 压位加法的进位
            tmp[dst][i] -= BASE;
            tmp[dst][i + 1] += 1;
            if (tlen[dst] < i + 2) tlen[dst] = i + 2;
        }
    }
}

void solve() {
    int n;
    scanf("%d", &n);

    // 邮局左侧切口是空的：只有空切面一种初始状态
    len[0] = 1;
    big[0][0] = 1;

    // 扫过第 1 … n-1 列；第 n 列右侧没有横边，只能收口
    if (n == 1) { // 只有一列 4 个路口连不成环，路线数为 0
        printf("0\n");
        return;
    }
    for (int col = 1; col <= n - 1; col++) {
        // 新列的临时结果整块清零，避免上一列残留值混进答案
        for (int s = 0; s < 7; s++)
            for (int i = 0; i < MAXL; i++) tmp[s][i] = 0;
        for (int s = 0; s < 7; s++) tlen[s] = 0;
        // 转移表：新 {01}、{23}、{03,12} 来自旧 {03} 和 {03,12}
        add_old(1, 2); add_old(1, 6);
        add_old(4, 2); add_old(4, 6);
        add_old(6, 2); add_old(6, 6);
        // 新 {03} 来自除 {03}、{03,12} 外的任意旧切面
        add_old(2, 0); add_old(2, 1); add_old(2, 3); add_old(2, 4); add_old(2, 5);
        // 新 {01,23} 来自旧 空切面、{01}、{23}、{01,23}
        add_old(5, 0); add_old(5, 1); add_old(5, 4); add_old(5, 5);
        // 新 {12} 只来自旧 {03}
        add_old(3, 2);
        // 空切面只在第一列左侧出现，转移后恒为 0

        for (int s = 0; s < 7; s++) {
            len[s] = tlen[s];
            for (int i = 0; i < len[s]; i++) big[s][i] = tmp[s][i];
        }
    }

    // 收口数 = {03} + {03,12}；每条回路顺、逆时针算两条路线，再乘 2
    // 用大数加法直接算 ans = 2 * (big[2] + big[6])
    ll ans[MAXL];
    int alen = 0;
    if (len[2] > len[6]) alen = len[2]; else alen = len[6];
    for (int i = 0; i < alen; i++) {
        ll s = 0;
        if (i < len[2]) s += big[2][i];
        if (i < len[6]) s += big[6][i];
        ans[i] = s;
    }
    for (int i = 0; i < alen; i++) ans[i] *= 2; // 方向因子 2
    for (int i = 0; i < alen; i++) {            // 逐位进位
        if (ans[i] >= BASE) {
            ans[i + 1] += ans[i] / BASE;
            ans[i] %= BASE;
            if (alen < i + 2) alen = i + 2;
        }
    }
    while (alen > 1 && ans[alen - 1] == 0) alen--; // 去掉前导零段

    printf("%lld", ans[alen - 1]); // 最高段不补零
    for (int i = alen - 2; i >= 0; i--) printf("%09lld", ans[i]); // 其余段补足 9 位
    printf("\n");
}

int main() {
    solve();
    return 0;
}

复杂度

时间复杂度： $O(N)$ 。共进行 $N - 1$ 次转移，每次是常数条大整数加减。 $N = 1000$ 时答案约 340 位十进制数，大整数加减也是常数级开销。
空间复杂度： $O(1)$ 额外变量（不计输入输出与答案本身占用的位数）。

总结

先做翻译：把「每个交叉口恰好一次并回到起点」翻译成「网格图上每个顶点度数为 2 的哈密顿回路」。
再做削减：4 行这个固定宽度让「按列扫描 + 切口配对」成为可行模型，切口状态只有 7 种，转移是常系数线性递推。
最后核对： $N = 1$ 输出 0（一列 4 个点连不成环）， $N = 4$ 输出 12，与样例一致。

图示解析

下面这张图概括从题意到答案的主线（节点不超过 12 个，只用来说明模型关系，不重复代码）：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22题意：邮局出发走遍每个路口一次再回到邮局
              |
              v
      翻译：网格图上的哈密顿回路
              |
              v
  观察：南北向街道只在同一列内（竖边不跨列）
              |
              v
   按列扫描：切口上只需记"横边两两配对的 7 种方式"
              |
              v
    每列用"每个路口度数为 2"本地筛掉非法组合
              |
              v
   逐列乘 7 种切面的转移矩阵（共 N-1 次，O(N)）
              |
              v
     第 N 列收口数 × 2（顺/逆时针各算一条）
              |
              v
               答案

看这张图时注意三点：横向的「翻译」一步把走法问题变成了选边问题，是所有后续推导的前提；中间的「按列扫描」依赖竖边不跨列这一几何事实；最后一行的乘 2 来自题目把方向不同的走法视为不同路线。

已扫过列数	$\varnothing$	$\{01\}$	$\{03\}$	$\{12\}$	$\{23\}$	$\{01,23\}$	$\{03,12\}$	本列收口
1	1	0	0	0	0	0	0	0
2	0	0	1	0	0	1	0	0
3	0	1	1	1	1	1	1	0
4	0	2	4	1	2	3	2	0
5	0	6	8	4	6	7	6	0
6	0	14	23	8	14	19	14	37

已扫过列数	$\varnothing$	$\{01\}$	$\{03\}$	$\{12\}$	$\{23\}$	$\{01,23\}$	$\{03,12\}$	本列收口
1	1	0	0	0	0	0	0	0
2	0	0	1	0	0	1	0	0
3	0	1	1	1	1	1	1	0
4	0	2	4	1	2	3	2	0
5	0	6	8	4	6	7	6	0
6	0	14	23	8	14	19	14	37