扩展卢卡斯定理

luckydrawbox · 2022-08-12 07:44:20 · 个人记录

函数

代码

ll qmi(ll a,ll b,ll p){
    ll ans=1%p;
    while(b){
        if(b&1)
            ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1;y=0;
        return a;
    }
    ll d=exgcd(b,a%b,x,y);
    ll tmp=x;
    x=y;
    y=tmp-a/b*x;
    return d;
}
ll inv(ll a,ll p_k){
    ll x,y;
    exgcd(a,p_k,x,y);
    return (x%p_k+p_k)%p_k;
}
ll fac(ll n,ll p,ll p_k){
    if(!n)
        return 1;
    ll ans=1;
    for(ll i=1;i<=p_k;i++)
        if(i%p)
            ans=ans*i%p_k;
    ans=qmi(ans,n/p_k,p_k);
    for(ll i=1;i<=n%p_k;i++)
        if(i%p)
            ans=ans*i%p_k;
    return ans*fac(n/p,p,p_k)%p_k;
}
ll qC(ll n,ll m,ll p,ll p_k){
    ll x=0,y=0,z=0;
    for(ll i=p;i<=n;i*=p)
        x+=n/i;
    for(ll i=p;i<=m;i*=p)
        y+=m/i;
    for(ll i=p;i<=(n-m);i*=p)
        z+=(n-m)/i;
    return fac(n,p,p_k)*inv(fac(m,p,p_k),p_k)%p_k
    *inv(fac(n-m,p,p_k),p_k)%p_k*qmi(p,x-y-z,p_k)%p_k;
}
long long CRT(int n,long long *a,long long *m){
    long long sum=0,M=1,x,y;
    for(int i=1;i<=n;i++)
        M*=m[i];
    for(int i=1;i<=n;i++){
        sum+=a[i]*M/m[i]%M*(inv(M/m[i],m[i]))%M;
    }
    return (sum%M+M)%M;
}
ll exlucas(ll n,ll m,ll P){
    ll tot=0;
    for(ll p=2;p*p<=P;p++){
        if(P%p)
            continue;
        ll p_k=1;
        while(P%p==0){
            p_k*=p;
            P/=p;
        }
        a[++tot]=qC(n,m,p,p_k);
        b[tot]=p_k;
    }
    if(P>1){
        a[++tot]=qC(n,m,P,P);
        b[tot]=P;
    }
    return CRT(tot,a,b);
}