HDU 3037 Saving Beans：Lucas 定理求大數組合數取模

HDU 3037 Saving Beans：Lucas 定理求大數組合數取模

求 C(n+m, m) mod p，其中 n, m ≤ 10^18，p 為質數。直接計算階乘不可行，需用 Lucas 定理分解。

數學原理

• 費馬小定理：a^(p-1) ≡ 1 (mod p) → a^(-1) ≡ a^(p-2) (mod p)。
• 組合數取模：C(a,b) = a! / (b!(a-b)!) ≡ a! · (b!)^(p-2) · ((a-b)!)^(p-2) (mod p)。
• Lucas 定理：將 n, m 按 p 進制分解：n = n_k p^k + ... + n_0, m = m_k p^k + ... + m_0。則 C(n,m) ≡ ∏ C(n_i, m_i) (mod p)。遞歸公式：Lucas(n,m,p) = C(n%p, m%p, p) * Lucas(n/p, m/p, p) mod p。

算法流程

1. 預計算或動態求 C(n%p, m%p, p) (n%p, m%p < p ≤ 10^5 可直接循環相乘)。
2. 遞歸調用 Lucas(n, m, p) 直到 m=0 返回 1。
3. 最終答案為 Lucas(n+m, m, p)。

C++ 實現 (含快速冪)

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;

LL mod_pow(LL a, LL n, LL p) {
    LL res = 1;
    while (n) {
        if (n & 1) res = res * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return res;
}

LL C(LL n, LL m, LL p) {
    if (m > n) return 0;
    LL num = 1, den = 1;
    for (LL i = 0; i < m; i++) {
        num = num * (n - i) % p;
        den = den * (m - i) % p;
    }
    return num * mod_pow(den, p - 2, p) % p;
}

LL Lucas(LL n, LL m, LL p) {
    if (m == 0) return 1;
    return C(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        LL n, m, p; scanf("%lld%lld%lld", &n, &m, &p);
        printf("%lld\n", Lucas(n + m, m, p));
    }
    return 0;
}

注意事項

• p 為質數是 Lucas 定理與費馬小定理適用的前提。
• 遞歸深度 ≤ log_p(n) ≈ 60，棧安全。
• 使用 __int64 或 long long 防止溢位，中間乘法取模。