HDU 3037 Saving Beans：組合數學與 Lucas 定理求模質數組合數

題目轉化

將不超過 m 顆相同豆子放入 n 棵不同樹中。引入虛擬第 n+1 棵樹存放「未使用的豆子」，問題等價於：將 m 顆豆子放入 n+1 棵樹（允許為空）。插板法得方案數為 C(n+m, m)。需對質數 p 取模，p < 100000，n,m ≤ 1e9。

Lucas 定理

對於質數 p，C(N, K) mod p = ∏ C(N_i, K_i) mod p，其中 N_i, K_i 為 N, K 在 p 進制下的各位。將大組合數分解為多個小於 p 的組合數乘積。

模逆元：費馬小定理

p 為質數時，a^(p-1) ≡ 1 (mod p)，故 a^(-1) ≡ a^(p-2) (mod p)。組合數 C(a,b) = a! / (b!(a-b)!) mod p 可通過預計算階乘與快速冪求逆元得到。

C++ 核心代碼

using ll = long long;
const int MAXP = 100000;
ll fact[MAXP];

void init_fact(int p) {
    fact[0] = 1;
    for (int i = 1; i < p; ++i) fact[i] = fact[i-1] * i % p;
}

ll mod_pow(ll a, ll e, int p) {
    ll r = 1;
    while (e) {
        if (e & 1) r = r * a % p;
        a = a * a % p;
        e >>= 1;
    }
    return r;
}

ll C_small(ll a, ll b, int p) {  // a,b < p
    if (a < b) return 0;
    return fact[a] * mod_pow(fact[b] * fact[a-b] % p, p-2, p) % p;
}

ll Lucas(ll n, ll m, int p) {
    if (m == 0) return 1;
    return Lucas(n/p, m/p, p) * C_small(n%p, m%p, p) % p;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        ll n, m, p; cin >> n >> m >> p;
        init_fact(p);
        cout << Lucas(n + m, m, p) << '\n';
    }
}

複雜度

• 預計算：O(p)，p ≤ 1e5。
• 每查詢：O(log_p(n+m)) 遞歸深度。

總結

大數組合數取模質數的標準套路：Lucas 定理分解 + 費馬小定理求逆元。注意預計算階乘陣列大小以 p 為界。