Saving Beans HDU3037(组合数公式+Lucas定理)

题意:

将至多m个豆子(即0-m都可以)放到n棵树上（一棵树可以一颗也不放），问有多少种放的方法。

答案对p取模，n,m<=1e10，p<=1e5，保证p为素数

思路:

用隔板法可以得到，将m颗豆子放到n棵树上的方案数为C(n+m-1,n-1)=C(n+m-1,m)。则答案为\(\sum C(n+i-1,i)\)

利用组合数公式化简为C(n+m,m)

现在问题就是n和m很大， 线性时间无法求出阶乘。注意到p很小，因此可以利用lucas定理进行加速组合数的求解。

Lucas定理

\(C(s*p+q,t*p+r)\equiv C(s,t)*C(q,r) \pmod p\)

(C(n,m)当m大于n时组合数为0？)

即C(n,m)可以转换为$C(n/p,m/p)*C(n $% \(p,m\) % $p) $，后者是一个很小的组合数，可以通过预处理的阶乘来求解，而前者在以指数速度减小，因此可以递归求解，时间复杂度为O(log n)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
ll fact[maxn];
ll mod;
ll fp(ll b, ll x) {
    ll ans = 1;
    while (x) {
        if (x & 1) {
            ans = ans * b%mod;
        }
        b = b * b%mod;
        x >>= 1;
    }
    return ans;
}
ll inv(ll x) {
    return fp(x, mod - 2);
}
void init() {
    fact[0] = 1;
    for (int i = 1; i <= mod; i++) {
        fact[i] = fact[i - 1] * i %mod;
    }
}
ll lucas(ll n, ll m) {
    ll ans = 1;
    while (n&&m) {
        ll n1 = n % mod;
        ll m1 = m % mod;
        if (n1 - m1 < 0) {
            return 0;
        }
        ans = ans * fact[n1] % mod * inv(fact[n1 - m1] * fact[m1] % mod) % mod;
        n /= mod;
        m /= mod;
    }
    return ans;
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        ll n, m;
        scanf("%lld%lld%lld", &n, &m, &mod);
        init();
        ll ans = lucas(n + m, m);
        printf("%lld\n", ans);
    }
}

Saving Beans HDU3037(组合数公式+Lucas定理)

原文：https://www.cnblogs.com/ucprer/p/12269667.html