算法

(DFS,剪枝) $O(n!)$

依次枚举每个字母代表哪个数字。

手动做加法竖式时按照从右到左的顺序，因此我们也按照从右到左出现的次序枚举每个字母的选法，这样可以方便后续的剪枝：

• 从后往前枚举每一列，记当前这列的被加数、加数、和分别为 $a, b, c$，如果右边所有数均已确定，则当前这位的进位也是确定的，记为 $t$，则如果 $a + b + t \neq c$，那么当前方案不合法；
• 如果右边存在某个未知数尚未确定，则上一位的进位 $t$ 可能取0或1，那么如果 $a + b \neq c, a + b + 1 \neq c$ 同时成立，则说明当前方案不合法；
• 另外对于最高位，判断是否有进位，如果有进位，则说明不合法（因为和也是 $n$ 位数）
• 最后，对于每个字母要从大到小枚举所有可能的取值。因为优先枚举较大的数，更有利于提前确定最高位是否进位，从而提早剪掉不合法的方案。

此时DFS就可以在1s内通过所有测试数据了。

时间复杂度

最坏情况下需要枚举 $n!$ 种方案，但由于剪枝的存在，实际搜索到的空间很小。

C++ 代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 30;

int n;
char eq[3][N];
int q[N], path[N];
bool st[N];

bool check()
{
    for (int i = n - 1, t = 0; i >= 0; i -- )
    {
        int a = path[eq[0][i] - 'A'], b = path[eq[1][i] - 'A'], c = path[eq[2][i] - 'A'];
        if (a != -1 && b != -1 && c != -1)
        {
            if (t == -1)
            {
                if ((a + b) % n != c && (a + b + 1) % n != c) return false;
                if (!i && a + b >= n) return false; // 最高位有进位
            }
            else
            {
                if ((a + b + t) % n != c) return false;
                if (!i && a + b + t >= n) return false;
                t = (a + b + t) / n;
            }
        }
        else t = -1;
    }

    return true;
}

bool dfs(int u)
{
    if (u == n) return true;

    for (int i = n - 1; i >= 0; i -- )
        if (!st[i])
        {
            st[i] = true;
            path[q[u]] = i;
            if (check() && dfs(u + 1)) return true;
            path[q[u]] = -1;
            st[i] = false;
        }

    return false;
}

int main()
{
    cin >> n >> eq[0] >> eq[1] >> eq[2];

    for (int i = n - 1, k = 0; i >= 0; i -- )
        for (int j = 0; j < 3; j ++ )
        {
            int c = eq[j][i] - 'A';
            if (!st[c])
            {
                st[c] = true;
                q[k ++ ] = c;
            }
        }

    memset(st, 0, sizeof st);
    memset(path, -1, sizeof path);

    dfs(0);

    for (int i = 0; i < n; i ++ ) cout << path[i] << ' ';

    return 0;
}