Moe's CF Life

喵~ 主人，今天我们来研究一道非常有趣的数论组合题，Codeforces 上的 1907E - Good Triples。别看它好像和数字的位数有关，有点复杂的样子，其实只要找到一个小小的突破口，问题就会变得像撸猫一样顺滑哦！让本喵带你一步步解开它的谜底吧！

题目大意

题目是这样哒：

给我们一个非负整数 n (n ≥ 0)。我们要找到有多少个 “好” 的三元组 (a, b, c)，它们需要满足两个条件：

a, b, c 都是非负整数，并且它们的和等于 n，也就是 a + b + c = n。
a, b, c 各自的数位和（digsum）加起来，正好等于 n 的数位和。也就是 digsum(a) + digsum(b) + digsum(c) = digsum(n)。

digsum(x) 就是把数字 x 的每一位都加起来。比如 digsum(123) = 1 + 2 + 3 = 6。

题目还特别提醒，三元组中数字的顺序是重要的，所以 (4, 12, 10) 和 (10, 12, 4) 是两个不同的三元组。

解题思路

看到 digsum(a) + digsum(b) + digsum(c) = digsum(n) 这个条件，是不是感觉有点头大呀？别怕别怕，本喵有一个神奇的魔法，可以把它变简单！这个魔法就是 “无进位加法”！喵~

关键性质：数位和与进位

我们来想一下，平时做加法的时候，数位和会发生什么变化。比如 12 + 9 = 21：

digsum(12) = 1 + 2 = 3
digsum(9) = 9
digsum(12) + digsum(9) = 12
digsum(21) = 2 + 1 = 3

你看，3 + 9 ≠ 3。这是因为 2+9 产生了进位。

实际上，有一个非常重要的结论： 当且仅当两个数 x 和 y 相加时，每一位都没有产生进位，才会有 digsum(x) + digsum(y) = digsum(x+y)。

这个性质可以推广到三个数哦。所以，题目中的第二个条件 digsum(a) + digsum(b) + digsum(c) = digsum(n)，再结合第一个条件 a + b + c = n，就可以等价地转换成：

整数 a, b, c 相加得到 n 的过程中，没有发生任何进位。

哇，问题是不是一下子清晰多啦？

按位分解问题

既然加法没有进位，这意味着每一位的计算都是独立的！我们可以把 n 的每一位拆开来单独考虑。

比如 n = 26。我们可以把它看成是 2 个十和 6 个一。

对于个位：我们需要找到三个非负整数 a_0, b_0, c_0，使得 a_0 + b_0 + c_0 = 6。（a_0, b_0, c_0 分别是 a, b, c 的个位数字）
对于十位：我们需要找到三个非负整数 a_1, b_1, c_1，使得 a_1 + b_1 + c_1 = 2。（a_1, b_1, c_1 分别是 a, b, c 的十位数字）

每一位的方案数算出来后，根据乘法原理，把它们全部乘起来就是最终的答案了。

组合数学：隔板法

现在问题就变成了：对于 n 的某一位数字 d，求方程 x + y + z = d 的非负整数解的个数。

这是一个经典的组合数学问题，可以用 “隔板法”（Stars and Bars）来解决，喵~

想象一下，我们有 d 个相同的小球（星星 ★），要把它们分成 3 份。这等价于用 2 个隔板 | 来分割它们。例如，d=6，a_0+b_0+c_0=6。一个可能的解是 2+3+1=6，可以表示为： ★★ | ★★★ | ★

我们实际上是在排列 d 个星星和 2 个隔板。总共有 d+2 个位置，我们只需要选择 2 个位置放隔板，剩下的位置自然就是星星了。所以，方案数就是组合数 C(d+2, 2)。

C(d+2, 2) = (d+2)! / (2! * (d+2-2)!) = (d+2) * (d+1) / 2

最终算法

所以，我们的算法就很简单啦：

初始化总方案数 total_ways = 1。
遍历整数 n 的每一位数字 d。
对于每一位数字 d，计算其对应的方案数 ways_for_digit = (d + 2) * (d + 1) / 2。
将 total_ways 乘上 ways_for_digit。
遍历完所有位数后，total_ways 就是我们要求的答案！

举个例子 n = 11：

个位是 1。d=1。方案数 C(1+2, 2) = C(3,2) = 3。
十位是 1。d=1。方案数 C(1+2, 2) = C(3,2) = 3。
总方案数 = 3 * 3 = 9。和样例一样，完美！

代码实现

好啦，理论分析完毕，我们来看看代码是怎么实现的吧，喵~

cpp

#include <iostream>

// 这个函数解决一个测试用例
void solve() {
    int n;
    std::cin >> n;

    // 结果可能会很大，所以我们用 64 位整数 long long
    long long total_ways = 1;

    // 核心逻辑：
    // a+b+c=n 和 digsum(a)+digsum(b)+digsum(c)=digsum(n) 等价于
    // a, b, c 的十进制加法中没有进位。
    // 这意味着我们可以独立地按位解决问题。
    // 对于 n 的每一位数字 d，我们需要找到 a_i + b_i + c_i = d 的非负整数解的数量。
    // 这是一个经典的隔板法问题，解的数量是 C(d+2, 2)。
    // C(d+2, 2) = (d+2)*(d+1)/2。
    // 总的三元组数量是每一位方案数的乘积。

    // 我们使用 do-while 循环来正确处理 n=0 的情况。
    // 如果 n=0，循环会为数字 0 执行一次。
    do {
        int digit = n % 10;
        
        // 计算 C(digit + 2, 2)
        long long ways_for_digit = (long long)(digit + 2) * (digit + 1) / 2;
        
        total_ways *= ways_for_digit;
        
        n /= 10;
    } while (n > 0);

    std::cout << total_ways << "\n";
}

int main() {
    // 快速 I/O
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

代码中的 do-while 循环是一个很棒的小技巧哦，它可以优雅地处理 n=0 的情况。当 n=0 时，循环体也至少会执行一次，计算 d=0 的情况（C(0+2, 2) = 1），得到正确答案 1，非常方便！

题目大意

解题思路

关键性质：数位和与进位

按位分解问题

组合数学：隔板法

最终算法

代码实现

相关知识点介绍

1. 数位和与无进位加法 (Digital Sum & Carry-less Addition)

2. 组合数学 - 隔板法 (Combinatorics - Stars and Bars)

题目大意 ​

解题思路 ​

关键性质：数位和与进位 ​

按位分解问题 ​

组合数学：隔板法 ​

最终算法 ​

代码实现 ​

相关知识点介绍 ​

1. 数位和与无进位加法 (Digital Sum & Carry-less Addition) ​

2. 组合数学 - 隔板法 (Combinatorics - Stars and Bars) ​

题目大意

解题思路

关键性质：数位和与进位

按位分解问题

组合数学：隔板法

最终算法

代码实现

相关知识点介绍

1. 数位和与无进位加法 (Digital Sum & Carry-less Addition)

2. 组合数学 - 隔板法 (Combinatorics - Stars and Bars)