HDU 3037 Saving Beans：組合數 + Lucas 定理

問題描述

松鼠要把不超過 m 顆相同的豆子存放在 n 棵不同的樹上（每棵樹可放 0 顆）。求方案數模 p（p 為質數，p < 100,000）。1 ≤ n,m ≤ 10^9，多測試用例。

數學轉化

方案數 = ∑_{k=0}^{m} C(n+k-1, k)（插板法：n 棵樹放 k 顆豆）。

利用組合數恆等式：

C(n-1,0) + C(n,1) + ... + C(n+m-1,m) = C(n+m, m)

證明：C(n+k, k) = C(n+k-1, k) + C(n+k-1, k-1) 遞推疊加。

因此問題簡化為求 C(n+m, m) mod p。

Lucas 定理

對於質數 p，將 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)。若某位 m_i > n_i 則 C(n_i, m_i) = 0。

遞歸形式：Lucas(N, M, p) = C(N%p, M%p) * Lucas(N/p, M/p, p) mod p，邊界 M=0 時為 1。

模質數下的組合數計算

C(a, b) = a! / (b! (a-b)!) mod p。利用費馬小定理：x^{-1} ≡ x^{p-2} (mod p)。預處理階乘 fact[i] = i! mod p，則：

C(a, b) = fact[a] * powmod(fact[b], p-2) % p * powmod(fact[a-b], p-2) % p

因 p < 100,000，預處理 O(p) 完全可行。

關鍵代碼片段 (C++)

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

LL mod;
vector<LL> fact;

LL powmod(LL a, LL e) {
    LL r = 1;
    while (e) {
        if (e & 1) r = r * a % mod;
        a = a * a % mod;
        e >>= 1;
    }
    return r;
}

LL C_small(LL a, LL b) {  // a,b < mod
    if (a < b) return 0;
    return fact[a] * powmod(fact[b] * fact[a-b] % mod, mod-2) % mod;
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        LL n, m; cin >> n >> m >> mod;
        fact.assign(mod, 1);
        for (int i = 1; i < mod; ++i) fact[i] = fact[i-1] * i % mod;
        cout << Lucas(n + m, m) << '\n';
    }
    return 0;
}

複雜度分析

• 預處理階乘：O(p)，p < 10^5。
• Lucas 遞歸深度 O(log_p (n+m)) ≤ 5，每層 O(1)。
• 總時間 O(T·p)，空間 O(p)。

總結

HDU 3037 將「不超過 m 顆豆」轉化為單一組合數 C(n+m, m)，再利用 Lucas 定理在大數模質數下計算。關鍵步驟：插板法建模、組合數恆等式求和簡化、Lucas 定理分解大數、費馬小定理計算模逆元。代碼結構清晰，是組合數學與數論結合的經典例題。