虫食算

形式化题目

给定一个正整数 $N$ ( $N \le 26$ )，以及三个长度为 $N$ 的由大写英文字母（取自字母表的前 $N$ 个字母）组成的字符串 $s_1, s_2, s_3$ 。这三个字符串分别代表两个加数和它们的和。这是一个 $N$ 进制的加法算式，允许存在前导零。我们需要找到一个从字母表前 $N$ 个大写字母到集合 $\{0, 1, \dots, N-1\}$ 的双射 $f$ ，满足 $f$ 将给定的算式转换为合法的 $N$ 进制加法。保证存在且仅存在唯一一组解。输出按字母表顺序排列的 $A, B, C, \dots$ 所代表的数字。

正解

思路

本题最直观的做法是枚举 $0$ 到 $N-1$ 的全排列并映射到每个字母，然后判断加法算式是否成立，但由于 $N \le 26$ ， $26!$ 的搜索空间是极其巨大的。 瓶颈在哪：如果最后才对整个算式进行验证，在搜索树的极早期所做的大部分无效决策都无法被发现，导致极大的时间浪费。

为了优化搜索，我们应当尽早验证以进行剪枝。

搜索顺序的优化：加法的计算是由低位向高位进行的，因此最右侧低位的字符应当被优先确定。我们可以从右往左遍历三行字符串提取出现的字母，依次作为搜索枚举赋值的顺序。通过尽早凑齐某一列的三个字母，便可以针对该列实施可行性检查。
强力剪枝：在 DFS 过程中维护一个 check() 函数遍历当前所有列。如果某列的三个字母都被赋了值：
- 能够确切知道上一位的进位时，直接验证本位运算和结果是否相符。
- 不能确切知道上一位的进位时（但进位必为 0 或 1），验证当前位的和在加 0 或加 1 的情况下，是否有能与目标字母匹配的可能。
推断式剪枝：如果在某列上只有两个字母被赋值，可以通过进位情况反推第三个字母应该是什么数字。如果推断出来的那个唯一（或两个候选）数字已经被其他字母占用了，则说明当前状态必无解，直接剪枝返回，这能够有效地将矛盾提前暴露出来。

结合上述三点，在倒序枚举字母所代表的数字（从 $N-1$ 倒着试探至 $0$ ）时，配合高频度且低开销的 check()，能在微秒级别快速找到唯一解。

代码

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

import sys

def solve() -> None:
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    n = int(input_data[0])
    s1, s2, s3 = input_data[1], input_data[2], input_data[3]

    val = [-1] * n
    used = [False] * n

    vis_order = [False] * 26
    order = []
    for i in range(n - 1, -1, -1):
        for s in (s1, s2, s3):
            idx = ord(s[i]) - ord('A')
            if not vis_order[idx]:
                vis_order[idx] = True
                order.append(idx)

    def check() -> bool:
        carry = 0
        for i in range(n - 1, -1, -1):
            v1 = val[ord(s1[i]) - ord('A')]
            v2 = val[ord(s2[i]) - ord('A')]
            v3 = val[ord(s3[i]) - ord('A')]
            if v1 != -1 and v2 != -1 and v3 != -1:
                if carry != -1:
                    sm = v1 + v2 + carry
                    if sm % n != v3:
                        return False
                    carry = sm // n
                else:
                    if (v1 + v2) % n != v3 and (v1 + v2 + 1) % n != v3:
                        return False
            else:
                carry = -1
                if v1 != -1 and v2 != -1:
                    t1 = (v1 + v2) % n
                    t2 = (v1 + v2 + 1) % n
                    if used[t1] and used[t2]:
                        return False
                elif v1 != -1 and v3 != -1:
                    t1 = (v3 - v1 + n) % n
                    t2 = (v3 - v1 - 1 + n) % n
                    if used[t1] and used[t2]:
                        return False
                elif v2 != -1 and v3 != -1:
                    t1 = (v3 - v2 + n) % n
                    t2 = (v3 - v2 - 1 + n) % n
                    if used[t1] and used[t2]:
                        return False
        return True

    def verify() -> bool:
        carry = 0
        for i in range(n - 1, -1, -1):
            v1 = val[ord(s1[i]) - ord('A')]
            v2 = val[ord(s2[i]) - ord('A')]
            v3 = val[ord(s3[i]) - ord('A')]
            sm = v1 + v2 + carry
            if sm % n != v3:
                return False
            carry = sm // n
        return carry == 0

    def dfs(u: int) -> bool:
        if u == n:
            return verify()
        if not check():
            return False
        
        c = order[u]
        for i in range(n - 1, -1, -1):
            if not used[i]:
                val[c] = i
                used[i] = True
                if dfs(u + 1):
                    return True
                used[i] = False
                val[c] = -1
        return False

    dfs(0)
    print(" ".join(str(val[i]) for i in range(n)))

if __name__ == '__main__':
    solve()

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#include <iostream>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

int n;
string s1, s2, s3;
int val[26];
bool used[26];
int order[26];
int order_cnt = 0;

bool check() {
    int carry = 0;
    for (int i = n - 1; i >= 0; --i) {
        int v1 = val[s1[i] - 'A'];
        int v2 = val[s2[i] - 'A'];
        int v3 = val[s3[i] - 'A'];
        if (v1 != -1 && v2 != -1 && v3 != -1) {
            if (carry != -1) {
                int sum = v1 + v2 + carry;
                if (sum % n != v3) return false;
                carry = sum / n;
            } else {
                if ((v1 + v2) % n != v3 && (v1 + v2 + 1) % n != v3) {
                    return false;
                }
            }
        } else {
            carry = -1;
            if (v1 != -1 && v2 != -1) {
                int t1 = (v1 + v2) % n;
                int t2 = (v1 + v2 + 1) % n;
                if (used[t1] && used[t2]) {
                    return false;
                }
            } else if (v1 != -1 && v3 != -1) {
                int t1 = (v3 - v1 + n) % n;
                int t2 = (v3 - v1 - 1 + n) % n;
                if (used[t1] && used[t2]) {
                    return false;
                }
            } else if (v2 != -1 && v3 != -1) {
                int t1 = (v3 - v2 + n) % n;
                int t2 = (v3 - v2 - 1 + n) % n;
                if (used[t1] && used[t2]) {
                    return false;
                }
            }
        }
    }
    return true;
}

// 模拟完整加法验证，严格校验所有进位
bool verify() {
    int carry = 0;
    for (int i = n - 1; i >= 0; --i) {
        int v1 = val[s1[i] - 'A'];
        int v2 = val[s2[i] - 'A'];
        int v3 = val[s3[i] - 'A'];
        int sum = v1 + v2 + carry;
        if (sum % n != v3) return false;
        carry = sum / n;
    }
    return carry == 0;
}

bool dfs(int u) {
    if (u == n) {
        return verify();
    }
    if (!check()) return false;
    
    int c = order[u];
    for (int i = n - 1; i >= 0; --i) {
        if (!used[i]) {
            val[c] = i;
            used[i] = true;
            if (dfs(u + 1)) return true;
            used[i] = false;
            val[c] = -1;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> n)) return 0;
    cin >> s1 >> s2 >> s3;

    for (int i = 0; i < n; ++i) {
        val[i] = -1;
        used[i] = false;
    }

    bool vis_order[26] = {false};
    for (int i = n - 1; i >= 0; --i) {
        if (!vis_order[s1[i] - 'A']) {
            vis_order[s1[i] - 'A'] = true;
            order[order_cnt++] = s1[i] - 'A';
        }
        if (!vis_order[s2[i] - 'A']) {
            vis_order[s2[i] - 'A'] = true;
            order[order_cnt++] = s2[i] - 'A';
        }
        if (!vis_order[s3[i] - 'A']) {
            vis_order[s3[i] - 'A'] = true;
            order[order_cnt++] = s3[i] - 'A';
        }
    }

    dfs(0);

    for (int i = 0; i < n; ++i) {
        cout << val[i] << (i == n - 1 ? "" : " ");
    }
    cout << "\n";
    return 0;
}

复杂度

时间复杂度：最坏情况下时间复杂度为 $O(N! \cdot N)$ 。但在极其强力的可行性剪枝作用下，搜索树极窄，实际运行的枚举次数远小于理论上界，通常能在很短的时间内搜到合法解，平摊认为复杂度属于有效常数范围内的极小规模搜索。
空间复杂度：需要若干个长度为 $N$ 的数组来记录映射关系和占用情况，加上递归调用的栈空间最大深度为 $N$ ，因此空间复杂度为 $O(N)$ 。

总结

搜索顺序决定成败：如果不按照从低位到高位的出现顺序安排变量的赋值，剪枝很难发挥效用，必然会引发超时。
剪枝条件的完备性：利用“进位只有 0 和 1”这一特性，对即使未全部赋好值的列做预先判断，是此类“算式迷题”最通用的解法核心。
注意模运算中的负数：在反推需要的数字时，形如 (v3 - v1 + N) % N 这种加 $N$ 的技巧，可以安全防止在 C++ 中出现负数取模而导致非预期结果的坑。

★★ 数据生成记录（原本无答案文件）

情况

new_ROJ/problems/3077/data/ 原本只有 10 个 alpha*.in， 既无 .out 也无 .ans，素材侧也没有官方 std.cpp ⇒ 本篇题解所需的答案由父会话生成。

生成方式

写「列校验 + 剪枝 DFS」解（n 进制虫食算的经典解法）
★ 过程中发现并修正了自己解法的 bug： check() 在进位未知（前一位有未定字母）时只试了进位 0，会误杀合法的进位 1 状态，导致 alpha3–alpha8 全部返回 -1 （而题面保证「有且仅有一组解」）⇒ 改为两种进位都接受后 10/10 出解
★★ 独立验证（不复用 DFS 逻辑）：把字母按解换成数字，做 n 进制加法换算，并检查是 0..n-1 的双射 ⇒ 10/10 ✅（含 n=21 两组）

★ 证据等级的诚实声明（`T14`）

项	等级
生成的答案经独立进制换算 + 双射验证	★★★★
与官方 `std.cpp` 对拍	★（本题无 `std.cpp`）
与官方 `.out` 逐字节比对	★（原本不存在）

⇒ ★ 本題的答案不是官方数据，而是父会话生成并经独立校验的。 main.cpp / main.py 在此数据上 10/10 通过，但这只证明「与生成的答案一致」，不能声称「与官方数据一致」（T65）。

★ 生成脚本与校验脚本：docs/plans/roj-283/artifacts/3077-sol.cpp · docs/plans/roj-283/artifacts/3077-verify.py（已从 /tmp 归档）

目录

形式化题目

正解

思路

代码

复杂度

总结

★★ 数据生成记录（原本无答案文件）

情况

生成方式

★ 证据等级的诚实声明（T14）

★ 证据等级的诚实声明（`T14`）