首先问题可以转化成“n + m 次决策，其中有 m 次向右”，也就变成了计算 C(n + m, m)，当然根据组合数的对称性也可以计算 C(n + m, n).

0 <= n,m <= 2^{32} 所以直接计算组合数或者递推都不太可能。

然后 C(x, 0), C(x, 1), C(x, x) 是可能存在的 corner case 而且是能 O(1) 得到答案的特殊情况，考虑特判。

对于组合数 C(N, x) 来说，根据 C(N, N-x) = C(N, x) 的对称性和公式的分母变化可以得出它是一个单峰函数，当取到 C(N, N/2) 时最大。又因为题目答案不超过 32 位无符号整数，所以 C(N, N/2) 里的 N/2 最多也就是 34。

比较精华的是考虑怎么计算 C(n + m, min(n, m)) 这个式子。令 m < n ，可以推式子得到如下：
C(n + m, m) = (n + m) 的 m 次下降幂 / m 的阶乘

所以可以只考虑 m 个多项式相乘的分母和一个阶乘分子即可。

既然 m 比较小，就考虑能不能将分子和 {1, 2, 3, ..., m} （也就是分母阶乘的每个部分）进行约分，使得计算过程不会溢出 32 位无符号整数。而且必然是可以约分的，因为分式的结果是个整数。而且每轮约分优先从大数字开始，因为它们可能含有更多的因子，不过 m 不大也无所谓了。

最后答案就是分子 m 个元素相乘。

```core code (cpp)
typedef unsigned u32;

u32 gcd(u32 a, u32 b) { return b == 0 ? a : gcd(b, a % b); }

u32 solve(u32 n, u32 m) {
    // 1. corner case
    if (n == m || m == 0) return 1;
    if (m == 1) return n;

    // ans = C(n + m, min(n, m)) = (n+m)! / n!m!
    std::vector<u32> denom(m); // 2. m is smaller
    for (u32 i = 0; i < m; i++) denom[i] = n - i;
    for (u32 i = 2; i <= m; i++) {
        for (u32 j = 0, d = i; j < m && d > 1; j++) {
            u32 g = gcd(d, denom[j]);
            d /= g;
            denom[j] /= g;
        }
    }
    u32 res = 1;
    for (int i = 0; i < m; i++) res *= denom[i];
    return res;
}

int main() {
    int _ = 1;
    // scanf("%d", &_);

    for (u32 n, m; ; ) {
        scanf("%u%u", &n, &m);
        if (n == 0 && m == 0) break;
        printf("%u\n", solve(n + m, std::min(n, m)));
    }
    return 0;
}
```

• Re:组合数求解，及其优化。 (119) ShenNaizhi 2025-08-03 16:55:00