【题解】[ROIR 2021 Day 2] A + B

Statement

给定可能含前导零的三个位数为 $n$ 的整数 $A,B,C$ ，求出排列 $p$ 的个数，使得三个整数的每一位经过排列映射后得到的 $A',B',C'$ 可以使 $A' + B' = C'$ 成立，答案对 $10^9 + 7$ 取模。

下文中定义位数从右向左，例如 $A_1$ 表示 $A$ 的个位上的数， $A_n$ 为最高位的数。

Solution

一道并不难的排列组合计数题，复杂就在处理不同数位之间的进位问题。

不进位的情况

先考虑不进位的情况，每一位之间都不会互相影响，同时由于 $A',B',C'$ 不能含有前导零，我们定义 $zero$ 表示有 $0$ 的列数。

答案简洁明了，第一列放非 $0$ 列，后面随便放即可。

$ans = (n - zero) \times (n - 1)!$

进位的情况

如果会产生进位，那么对于 $10$ 以内的加法，会发生 $2 \times 2 = 4$ 中情况，它们分别是：

$A_i + B_i = C_i$ ：此时第 $i$ 和 $i - 1$ 位均不会进位，前文已经讨论过。
$A_i + B_i + 1 = C_i$ ：这一列成立的前提必须使第 $i - 1$ 位产生进位。
$A_i + B_i - 10 = C_i$ ：第 $i$ 位发生进位，同时第 $i - 1$ 不发生进位。
$A_i + B_i - 10 + 1 = C_i$ ：第 $i$ 位和第 $i - 1$ 位均发生进位。

如果发生了其他的情况，那么必然无解，输出 0 即可。

我们用数组 $cnt_{0 \sim 3}$ 分别记录这四种情况，可以发现无论什么等式，第二种情况和第三种情况的发生次数必然一样。

证明很简单，第二种情况要求 $i - 1$ 产生进位， $i$ 不产生进位，第三种情况要求 $i$ 产生进位， $i - 1$ 不产生进位。而由于第四种情况把进位关系传递了，可以忽略，因此：

$cnt_1 \ne cnt_2 \iff ans = 0$

继续分析，发现后面两种情况不能发生在最终等式的第 $n$ 位上，第 $2,4$ 种情况不能发生在最终等式的第 $1$ 位上，而由于不能有前导零的出现，我们定义 $zero$ 统计第 $1,2$ 情况含 $0$ 列的数量。

于是我们得出发生未发生进位（情况 $1,2$ ）的列所能得到的排列数量 $ans1$ ：

$ans1 = (cnt_0 + cnt_1 - zero) \times (cnt_0 + cnt_1 - 1)!$

以及发生过进位（情况 $3,4$ ）的列所能得到的排列数量 $ans2$ （这里要保证最后一列不能是情况 $4$ ）：

$ans2 = (cnt_2 + cnt_3 - 1) \times (cnt_2 + cnt_3 - 1)!$

由于前文证明的 $cnt_1 = cnt_2$ ，并且两次进位之间必然存在被进位的一列，因此最终序列从右到左应当为条件三和条件二交错，条件一和条件四具有传递关系，因此答案即为两者排列数量乘积：

$ans = ans1 \times ans2$

Code

int main()
{
    for (int i = fc[0] = 1; i < N; i ++) fc[i] = fc[i - 1] * i % mod;
    
    scanf("%s", str + 1), n = strlen(str + 1);
    for (int i = 1; i <= n; i ++) a[i] = str[i] ^ 48;
    for (int i = 1; i <= n; i ++) scanf("%1lld", b + i);
    for (int i = 1; i <= n; i ++) scanf("%1lld", c + i);
    
    for (int i = 1; i <= n; i ++)
    {
        if (a[i] + b[i] == c[i]) cnt[0] ++, zero += (!a[i] || !b[i] || !c[i]);
        else if (a[i] + b[i] + 1 == c[i]) cnt[1] ++, zero += (!a[i] || !b[i] || !c[i]);
        else if (a[i] + b[i] - 10 == c[i]) cnt[2] ++;
        else if (a[i] + b[i] - 10 + 1 == c[i]) cnt[3] ++;
        else return puts("0"), 0;
    }
    
    if (cnt[0] && !cnt[1] && !cnt[2] && !cnt[3])
        cout << (cnt[0] - zero) * fc[cnt[0] - 1] % mod << '\n';
    else if (cnt[1] == cnt[2])
        cout << (cnt[0] + cnt[1] - zero) * cnt[2] % mod * fc[cnt[2] + cnt[3] - 1] % mod * fc[cnt[0] + cnt[1] - 1] % mod << '\n';
    else puts("0");
    return 0;
}