HDU 3037 Saving Beans [Lucas定理]

不超过n个球放入m个盒子方案数，盒子可以为空

1 <= n, m <= 1000000000, 1 < p < 100000 and p is guaranteed to be a prime.

---

首先隔板法${n+m-1choose {m-1}}={n+m-1choose {n}}$

答案为$sumlimits_{i=0}^{n}{i+m-1choose {i}}$

这个求和列出来后发现可以用组合数的递推公式合并,因为${n-1choose 0}={nchoose 0}$

最后就是${m+nchoose m}$

注意不要预处理逆元啦会TLE(测试组数太多)，预处理阶乘行啦

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=100007;
inline ll read(){
    char c=getchar();ll x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
ll n,m,P;
ll fac[N];
void iniFac(int n){
    fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=i*fac[i-1]%P;
}
ll Pow(ll a,int b){
    ll re=1;
    for(;b;b>>=1,a=a*a%P)
        if(b&1) re=re*a%P;
    return re;
}
ll Inv(ll a){return Pow(a,P-2);}
ll C(ll n,ll m){
    if(n<m) return 0;
    return fac[n]*Inv(fac[m])%P*Inv(fac[n-m])%P;
}
ll Lucas(ll n,ll m){
    if(n<m) return 0;
    ll re=1;
    for(;m;n/=P,m/=P) re=re*C(n%P,m%P)%P;
    return re;
}
int main(){
    freopen("in","r",stdin);
    int T=read();
    while(T--){
        n=read();m=read();P=read();
        iniFac(P);
        printf("%lld
",Lucas(m+n,m));
    }
}