[NOIP2004-提高] 虫食算

形式化题目

给定 $N$ （ $N \le 26$ ）与三个长度恰为 $N$ 的大写字符串 $S_1, S_2, S_3$ ，字母全部取自字母表前 $N$ 个大写字母，且每个字母至少出现一次。把相同的字母换成相同的数字、不同的字母换成不同的数字后，要求

\mathrm{val}_N(S_1) + \mathrm{val}_N(S_2) = \mathrm{val}_N(S_3),

其中 $\mathrm{val}_N$ 表示 $N$ 进制数的值（允许前导 $0$ ）。求前 $N$ 个字母 $A,B,\dots$ 各自代表的数字（即一个双射 $f:\text{字母}\to\{0,\dots,N-1\}$ ），按 $A$ 到字母表第 $N$ 个字母的顺序输出。输入保证解唯一。

正解

思路

朴素做法：把前 $N$ 个字母的所有排列（ $N!$ 种赋值）逐一代入竖式验证。 $N \le 26$ 时 $26! \approx 4\times 10^{26}$ ，完全不可行，必须利用竖式本身的结构剪枝。

按列拆解。竖式逐列来看，第 $i$ 列（个位为第 $0$ 列）的三个数字 $a_i, b_i, s_i$ 与入进位 $c_i$ 、出进位 $c_{i+1}$ 满足

a_i + b_i + c_i = s_i + N \cdot c_{i+1}.

两个关键观察：

进位只有 $0$ 或 $1$ ：两个 $N$ 进制数相加最大为 $(N-1)+(N-1)+1 = 2N-1 < 2N$ ，所以任何一列的出进位都不超过 $1$ 。
和也是 $N$ 位，最高位出进位固定为 $0$ ；个位的入进位固定为 $0$ 。于是整条进位链两端都已知。

搜索方向。若从个位向高位搜，出进位要等低位填完才知道；反过来从最高位向低位搜，出进位一开始就是已知的（最高位列是 $0$ ），把第 $i$ 列的入进位 $c_i$ 由等式反解出来：

c_i = s_i + N \cdot c_{i+1} - a_i - b_i \in \{0,1\},

它恰好就是下一列（更低一位）的出进位——进位链沿着搜索方向一路传到个位，最后在个位验证 $c_0 = 0$ 即可。任何一列解出的 $c_i \notin \{0,1\}$ ，当前分支立即失败回溯。

每列的枚举。一列最多涉及 $3$ 个字母，但不必枚举它们的全排列：

三个字母都已确定：直接验证等式，只试两种入进位，不建任何枚举结构；
把已确定的字母折进常数项，方程化为 $\sum w_\ell \cdot f(\ell) = N c_{i+1} - c_i - \text{base}$ ，其中加数位字母系数 $+1$ 、结果位字母系数 $-1$ ，同一字母两边出现则抵消为 $0$ ；
留一个系数非零的字母最后由方程唯一解出（要求整除、落在 $[0,N)$ 、且没被认领），其余字母逐一枚举，枚举维度少一维；
系数被抵消的字母方程管不到，直接从空闲数字中枚举，但等式必须先成立，否则整个进位组合直接剪掉。

这样每列只枚举仍空闲的数字，靠"等式成立 + 进位是 $0/1$ "两重约束把 $N!$ 的搜索树砍到实际数据完全可接受的规模。

样例（ $N=5$ ，解为 $A{=}1,\,B{=}0,\,C{=}3,\,D{=}4,\,E{=}2$ ）逐列验证进位链（从个位到高位）：

列（低位→高位）	加数 1	加数 2	和	等式	出进位
第 0 列	$D{=}4$	$E{=}2$	$A{=}1$	$4+2+0 = 1 + 5\times 1$	$1$
第 1 列	$E{=}2$	$C{=}3$	$A{=}1$	$2+3+1 = 1 + 5\times 1$	$1$
第 2 列	$C{=}3$	$A{=}1$	$B{=}0$	$3+1+1 = 0 + 5\times 1$	$1$
第 3 列	$B{=}0$	$D{=}4$	$B{=}0$	$0+4+1 = 0 + 5\times 1$	$1$
第 4 列	$A{=}1$	$B{=}0$	$E{=}2$	$1+0+1 = 2 + 5\times 0$	$0$

最高位出进位为 $0$ （和恰好 $5$ 位）、个位入进位为 $0$ ，链条闭合， $10342_5 + 02134_5 = 20011_5$ 成立。

代码

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-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n;
int cola[30], colb[30], colc[30];   // 每列三个字母（低位在前）
int val[30];      // 字母 -> 数字，-1 未定
bool used[30];
int ans[30];

// 给本列未定字母 letters 分配数字，验证等式 Σ coeff[l]*val[l] == rhs 后递归下一列
bool assign_letters(const vector<int>& letters, const int coeff[30], int idx, int rhs, int pos, int carry_in);

// 从最高位列 pos 向低位搜；carry_out 是本列出进位（最高位固定 0）
bool dfs(int pos, int carry_out) {
    if (pos < 0) {
        for (int i = 0; i < n; i++) ans[i] = val[i];
        return true;
    }
    int a = cola[pos], b = colb[pos], c = colc[pos];
    int va = val[a], vb = val[b], vc = val[c];
    int nco = n * carry_out;
    int lo = 0;
    int hi = (pos == 0) ? 0 : 1;

    // 三个字母都已定：等式必须对某个入进位成立
    if (va >= 0 && vb >= 0 && vc >= 0) {
        int base = va + vb - vc;
        for (int carry_in = lo; carry_in <= hi; carry_in++)
            if (base == nco - carry_in && dfs(pos - 1, carry_in)) return true;
        return false;
    }

    // 本列未定字母的系数；已定字母折进常数项 base
    int coeff[30];
    memset(coeff, 0, sizeof(coeff));
    bool appear[30] = {false};
    int base = 0;
    if (va < 0) { coeff[a] += 1; appear[a] = true; } else base += va;
    if (vb < 0) { coeff[b] += 1; appear[b] = true; } else base += vb;
    if (vc < 0) { coeff[c] -= 1; appear[c] = true; } else base -= vc;

    vector<int> letters;
    for (int l = 0; l < n; l++)
        if (appear[l]) letters.push_back(l);

    for (int carry_in = lo; carry_in <= hi; carry_in++) {
        int rhs = nco - carry_in - base;
        if (assign_letters(letters, coeff, 0, rhs, pos, carry_in)) return true;
    }
    return false;
}

bool assign_letters(const vector<int>& letters, const int coeff[30], int idx, int rhs, int pos, int carry_in) {
    if (idx == (int)letters.size()) {
        int got = 0;
        for (size_t li = 0; li < letters.size(); li++)
            got += coeff[letters[li]] * val[letters[li]];
        if (got == rhs) return dfs(pos - 1, carry_in);
        return false;
    }
    int l = letters[idx];
    for (int d = 0; d < n; d++) {
        if (used[d]) continue;
        used[d] = true;
        val[l] = d;
        if (assign_letters(letters, coeff, idx + 1, rhs, pos, carry_in)) return true;
        val[l] = -1;
        used[d] = false;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    string s1, s2, s3;
    cin >> s1 >> s2 >> s3;
    reverse(s1.begin(), s1.end());
    reverse(s2.begin(), s2.end());
    reverse(s3.begin(), s3.end());
    for (int i = 0; i < n; i++) {
        cola[i] = s1[i] - 'A';
        colb[i] = s2[i] - 'A';
        colc[i] = s3[i] - 'A';
    }
    for (int i = 0; i < n; i++) { val[i] = -1; used[i] = false; }
    dfs(n - 1, 0);
    for (int i = 0; i < n; i++) {
        if (i) cout << " ";
        cout << ans[i];
    }
    cout << "\n";
    return 0;
}

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

import sys
from itertools import permutations


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

    # 三行都按低位在前重排列：从最高位往低位搜索，出进位先已知（最高位固定为 0），
    # 本列的入进位由等式反解出来，恰好等于下一列的出进位，进位链因此一路传到个位。
    cols = list(
        zip(*([ord(ch) - 65 for ch in next(data).decode()[::-1]] for _ in range(3)))
    )
    val = [-1] * n       # 字母 -> 数字；-1 表示还没定
    used = [False] * n   # 数字是否已被认领
    ans: list[int] = []

    # 热路径变量走形参默认值：递归调用点少传参，闭包变量也变成本地变量
    def dfs(pos: int, carry_out: int, cols=cols, n=n, val=val, used=used) -> bool:
        """从最高位列 pos 向低位搜（carry_out 是本列出进位），进位链接回个位且无多余进位时返回 True。"""
        if pos < 0:
            ans[:] = val  # 每列等式都成立、进位链两端都是 0，得到唯一解
            return True

        a, b, c = cols[pos]
        v_a, v_b, v_c = val[a], val[b], val[c]
        carries = (0,) if pos == 0 else (0, 1)  # 个位的入进位必为 0
        n_co = n * carry_out

        # 三个字母都已定：等式必须对某个入进位成立，直接验证，不建任何枚举结构
        if v_a >= 0 and v_b >= 0 and v_c >= 0:
            base = v_a + v_b - v_c
            for carry_in in carries:
                if base == n_co - carry_in and dfs(pos - 1, carry_in):
                    return True
            return False

        # 本列未定字母的系数：出现在加数位记 +1，出现在结果位记 -1，两边都出现则抵消成 0；
        # 已定字母折进常数项 base，方程化为 Σ 系数×字母 = n*出进位 - 入进位 - base
        coeff: dict[int, int] = {}
        base = 0
        for ch, vc in ((a, v_a), (b, v_b)):
            if vc < 0:
                coeff[ch] = coeff.get(ch, 0) + 1
            else:
                base += vc
        if v_c < 0:
            coeff[c] = coeff.get(c, 0) - 1
        else:
            base -= v_c

        pivots = [l for l, w in coeff.items() if w]  # 方程能解出的字母
        zero = [l for l, w in coeff.items() if not w]  # 被抵消的字母：本列方程管不到

        # 没有可解字母（未定字母全被抵消）：等式必须直接成立，否则先剪掉该进位组合
        if not pivots:
            for carry_in in carries:
                if n_co - carry_in != base:
                    continue
                for combo in permutations([d for d in range(n) if not used[d]], len(zero)):
                    for l, d in zip(zero, combo):
                        val[l] = d
                        used[d] = True
                    if dfs(pos - 1, carry_in):
                        return True
                    for l, d in zip(zero, combo):
                        val[l] = -1
                        used[d] = False
            return False

        # 只留一个字母最后解方程，枚举维度少一维
        pivot = pivots.pop()
        free = zero + pivots
        wp = coeff[pivot]
        rest = [d for d in range(n) if not used[d]]

        for carry_in in carries:
            rhs = n_co - carry_in - base
            for combo in permutations(rest, len(free)):
                got = 0
                for l, d in zip(free, combo):
                    w = coeff[l]
                    if w:
                        got += w * d
                rem = rhs - got
                if rem % wp:
                    continue
                digit = rem // wp  # 由方程唯一解出的最后一个字母
                if not 0 <= digit < n or used[digit] or digit in combo:
                    continue
                val[pivot] = digit
                used[digit] = True
                for l, d in zip(free, combo):
                    val[l] = d
                    used[d] = True
                if dfs(pos - 1, carry_in):  # 本列入进位就是下一列的出进位
                    return True
                for l, d in zip(free, combo):  # 回溯：撤销本列的赋值
                    val[l] = -1
                    used[d] = False
                val[pivot] = -1
                used[digit] = False
        return False

    dfs(n - 1, 0)
    print(' '.join(map(str, ans)))


if __name__ == "__main__":
    solve()

复杂度

设搜索树节点数为 $S$ （由"等式成立 + 进位为 $0/1$ "剪枝决定，随输入远小于 $N!$ ）：每个节点最多枚举空闲数字的两两组合 $O(N^2)$ ，总时间 $O(S \cdot N^2)$ ；空间为递归栈与若干长度 $O(N)$ 的数组， $O(N)$ 。最坏情况仍可能指数级，但本题数据保证唯一解且实际剪枝充分。

总结

把竖式按列拆开、把进位当作 $0/1$ 变量串成一条两端已知的链，是虫食算类问题的通用套路。从出进位已知的一端（最高位）向另一端搜索，入进位就能被等式唯一反解并立刻验证；每列再用"解方程代替枚举"把分支压到最少，两个观察叠加即可把 $N!$ 的朴素枚举压到可解规模。

[NOIP2004-提高] 虫食算

目录

形式化题目

正解

思路

代码

复杂度

总结