hdu3037 Saving Beans（Lucas定理）

hdu3037 Saving Beans

题意：n个不同的盒子，每个盒子里放一些球（可不放），总球数<=m，求方案数。

$1<=n,m<=1e9,1<p<1e5,p∈prime$

---

卢卡斯（Lucas）定理（计算组合数 防爆精度）

$lucas(n,m,p)=lucas(n/p,m/p,p)*C(n\%p,m\%p,p)$

$lucas(n,0,p)=1$

---

老套路，插板法。

设m个球都要放，多一个盒子轻松解决。

根据插板法得方案数$=C(n+m,n)$

跑一遍Lucas.

end.

#include<iostream>
#include<cstdio>
#include<cstring>
#define re register
using namespace std;
typedef long long ll;
int t,n,m,p;
ll fac[100002];
ll Pow(ll a,int b){
    ll res=1;
    for(;b;b>>=1){
        if(b&1) res=res*a%p;
        a=a*a%p;
    }return res%p;
}//快速幂求逆元
ll C(int n,int m){return n<m?0:fac[n]*Pow(fac[m],p-2)%p*Pow(fac[n-m],p-2)%p;} //注意n<m判0
ll lucas(int n,int m){
    if(!m) return 1;
    return lucas(n/p,m/p)*C(n%p,m%p)%p;
}
int main(){
    scanf("%d",&t); fac[0]=1;
    while(t--){
        scanf("%d%d%d",&n,&m,&p);
        re int i;
        for(i=1;i+4<=p;i+=4){
            fac[i]=fac[i-1]*i%p;
            fac[i+1]=fac[i]*(i+1)%p;
            fac[i+2]=fac[i+1]*(i+2)%p;
            fac[i+3]=fac[i+2]*(i+3)%p;
        }//循环展开加速
        for(;i<=p;++i) fac[i]=fac[i-1]*i%p;
        printf("%I64d
",lucas(n+m,n));
    }return 0;
}