原题链接
这题可以用爆搜或高斯消元，这里我用的是高斯消元。
对于题目中的样例：
ABCED
BDACE
EBBAA
我们可以将其转化为如下的方程组：
(egin{cases} A + B = E + k_1 \ B + D = B + k_2 \ C + A = B + k_3 \ E + C = A + k_4 \ D + E = A + k_5 end{cases})
(k_i)是因为进位的关系所加上去的数。若该位是进位的，(k_i = n)，若该位是被进位的，(k_i = -1)，若既进位有被进位，(k_i = n - 1)，若都没有则(k_i = 0)。
将未知数移到一边得（(k_i)看作常数）：
(egin{cases} A + B - E = k_1 \ D = k_2 \ C + A - B = k_3 \ E + C - A = k_4 \ D + E - A = k_5 end{cases})
转换为高斯消元的系数矩阵：
(egin{bmatrix} A & B & C & D & E & | & k_i \ hline 1 & 1 & 0 & 0 & -1 & | & k_1 \ 0 & 0 & 0 & 1 & 0 & | & k_2 \ 1 & -1 & 1 & 0 & 0 & | & k_3 \ -1 & 0 & 1 & 0 & 1 & | & k_4 \ -1 & 0 & 0 & 1 & 1 & | & k_5 end{bmatrix})
于是很容易想到一种做法，先搜索(k_i)的值，然后用高斯消元判断是否正确即可，但复杂度为(O(2 ^ n imes n ^ 3))，显然超时了。
考虑按上述思路逆向去做，将(k_i)也看作未知数，则矩阵转化为：
(egin{bmatrix} A & B & C & D & E & | & k_1 & k_2 & k_3 & k_4 & k_5 \ hline 1 & 1 & 0 & 0 & -1 & | & 1 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 1 & 0 & | & 0 & 1 & 0 & 0 & 0 \ 1 & -1 & 1 & 0 & 0 & | & 0 & 0 & 1 & 0 & 0 \ -1 & 0 & 1 & 0 & 1 & | & 0 & 0 & 0 & 1 & 0 \ -1 & 0 & 0 & 1 & 1 & | & 0 & 0 & 0 & 0 & 1 end{bmatrix})
进行一遍高斯消元后即可得到如下的关系式：
(egin{cases} A = k_1 - 2k_2 + k_3 - k_4 + 2k_5 \ B = k_1 - k_2 + k_5 \ C = k_2 + k_4 - k_5 \ D = k_2 \ E = k_1 - 3k_2 + k_3 - k_4 + 3k_5 end{cases})
然后再去搜索(k_i)的值代入关系式判断是否有解即可。
时间复杂度(O(n ^ 3 + 2 ^ n imes n ^ 2))，虽然依旧很高，但由于在检验(k_i)的值是否可行时，大多数情况都无法达到(n^2)（基本在判断第一个解时就能判断是错的），因此是能通过本题的。
另外，(k_i)的值取决于(k_{i - 1})的值，当(k_{i - 1})为(0)或(-1)时，(k_i)只能为(0)或(n)，当(k_{i - 1})为(n)或(n - 1)时，(k_i)只能为(-1)或(n - 1)，即前一位是否进位关系该位的取值。
所以虽然(k_i)有(4)个取值，但搜索的复杂度仅为(2^n)。
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 30;
int X[N][N], K[N][N], V[N], ans[N], n;
bool v[N];
inline char re()
{
char c = getchar();
for (; c < 'A' || c > 'Z'; c = getchar());
return c;
}
inline void sw(int& x, int& y) { int z = x; x = y; y = z; }
inline int jd(int x) { return x < 0 ? -x : x; }
inline int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
bool judge()
{
int i, j;
memset(v, 0, sizeof(v));
for (i = 1; i <= n; i++)
{
for (ans[i] = 0, j = 1; j <= n; j++)
ans[i] += V[j] * K[i][j];
if (ans[i] % X[i][i])
return false;
ans[i] /= X[i][i];
if (ans[i] < 0 || ans[i] >= n || v[ans[i]])
return false;
v[ans[i]] = 1;
}
return true;
}
bool dfs(int x, int y)
{
V[x] = y;
if (!(x ^ 1))
return judge();
if (dfs(x - 1, 0))
return true;
V[x] += n;
return dfs(x - 1, -1);
}
int main()
{
int i, j, k, lcn, x, y;
scanf("%d", &n);
for (i = 1; i < 3; i++)
for (j = 1; j <= n; j++)
X[j][re() - 'A' + 1]++;
for (i = 1; i <= n; i++)
X[i][re() - 'A' + 1]--, K[i][i] = 1;
for (i = 1; i <= n; i++)
{
for (k = i, j = i + 1; j <= n; j++)
if (jd(X[k][i]) < jd(X[j][i]))
k = j;
if (k ^ i)
for (j = 1; j <= n; j++)
sw(X[k][j], X[i][j]), sw(K[k][j], K[i][j]);
for (j = 1; j <= n; j++)
if (X[j][i] && j ^ i)
{
lcn = X[j][i] * X[i][i] / gcd(X[j][i], X[i][i]);
x = lcn / X[j][i]; y = lcn / X[i][i];
for (k = 1; k <= n; k++)
X[j][k] = X[j][k] * x - X[i][k] * y, K[j][k] = K[j][k] * x - K[i][k] * y;
}
}
dfs(n, 0);
for (i = 1; i <= n; i++)
printf("%d ", ans[i]);
return 0;
}