P4720【模板】扩展卢卡斯，P2183 礼物

suxxsfe · 2020-03-17 20:06:39 · 个人记录

扩展卢卡斯定理
最近光做模板了
想了解卢卡斯定理的去这里，那题也有我的题解
然而这题和卢卡斯定理并没有太大关系（雾
但是，首先要会的是中国剩余定理和exgcd

卢卡斯定理用于求n,m大，但模数p是质数，且较小的情况
但这题p并不保证是质数
所以，首先可以通过唯一分解定理给p分解乘若干质数相乘的形式：p=\prod p_i^{r_i}，当然r数列是分解后每个质数的指数
则我们可以对于每个p_i^{r_i}，求出\tbinom{n}{m} \bmod {p_i^{r_i}}，然后用crt进行合并，求出\tbinom{n}{m}\bmod p的值

所以，问题转化为：求\tbinom{n}{m} \bmod {p^{r}}，p为质数（~~为了写起来方便~~ 下文中所有p实际上都表示的是上文的p_i，r表示r_i）

又由于\tbinom{n}{m}=\dfrac{n!}{m!(n-m)!}
所以可以把n!中，所有是n的倍数的项都提出来，让它们都除以p，然后就又得到了一个长度为\lfloor \dfrac{n}{p}\rfloor的从一开始的自然数数列，然后递归的求解\lfloor \dfrac{n}{k}\rfloor!
那么，对于不是n的倍数的项，可以发现，它们\bmod p^r的值以p^r为一个循环节，所以我们只要求出这个循环节内所有数相乘的积，然后做一个快速幂求它的\lfloor \dfrac{n}{k}\rfloor次方就行了
而对于n \bmod k个长度不足一个循环节的数，直接把它乘起来就行了

然后求n!中因数p出现的次数是很容易的（具体见代码），那么除法就对应减去p出现的次数
而剩下的数（也就是刚才把p除掉来求的）中不含p，可以求\bmod p^r的逆元，就也能进行除法

最后记得能开long long的一定开long long
一遍过超开心
~~写了一晚上+一早上有什么可开心的。。。~~
另外这题的数据好像有些水，具体看这个帖，也不知道加强了没有

所以可以去看一下礼物这个题，loj和bzoj上都有
那题知道这个算法以后思维难度几乎为0，就是求

\tbinom{n}{w_1}\tbinom{n-w_1}{w_2}\tbinom{n-w_1-w_2}{w_3}\dots

然后这个礼物也成为了在洛谷A的第一个黑题~~虽然有些虚高~~
贴上代码
模板：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline LL read(){
    LL x=0,y=1;
    char c=std::getchar();
    while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
    return y?x:-x;
}
LL n,m,p;
inline LL power(LL a,LL b,LL pr){
    LL ret=1;
    while(b){
        if(b&1) ret=(ret*a)%pr;
        b>>=1;a=(a*a)%pr;
    }
    return ret;
}
void exgcd(LL a,LL b,LL &x,LL &y){
    if(!b) return x=1,y=0,void();
    exgcd(b,a%b,x,y);
    LL tmp=x;x=y;
    y=tmp-a/b*y;
}
inline LL getinv(LL nn,LL mod){
    LL x,y;
    exgcd(nn,mod,x,y);
    return (x+mod)%mod;
}
inline LL getfac(LL nn,LL pr,LL pp){//n!=x*p^y
    if(!nn) return 1;
    reg LL ans=1;
    for(reg LL i=2;i<pr;i++)
        if(i%pp) ans=ans*i%pr;
    ans=power(ans,nn/pr,pr);
    reg LL tmp=nn%pr;
    for(reg LL i=2;i<=tmp;i++)
        if(i%pp) ans=ans*i%pr;
    return ans*getfac(nn/pp,pr,pp)%pr;
}
inline LL C(LL nn,LL mm,LL pp,LL pr){
    LL x=getfac(nn,pr,pp),y=getfac(mm,pr,pp),z=getfac(nn-mm,pr,pp);
    LL num=0;//计算因数种有几个p
    for(reg LL i=nn;i;i/=pp) num+=i/pp;
    for(reg LL i=mm;i;i/=pp) num-=i/pp;
    for(reg LL i=nn-mm;i;i/=pp) num-=i/pp;
    return x*getinv(y,pr)%pr*getinv(z,pr)%pr*power(pp,num,pr)%pr; 
}
inline void crt(LL &ans,LL pr,LL ai){
    ans=(ans+(getinv(p/pr,pr)*ai%p*(p/pr)%p))%p;//这里p/pr就相当于crt里的Mi 
}
inline LL exlucas(){
    LL ans=0,pp=p,pr,sqrt=std::sqrt(p);//pr=p^r
    for(reg LL i=2;i<=sqrt;i++)if(!(pp%i)){
        pr=1;
        while(!(pp%i)) pp/=i,pr*=i;
        crt(ans,pr,C(n,m,i,pr));
    }
    if(pp>1) crt(ans,pp,C(n,m,pp,pp));//还有因数 
    return ans;
}
int main(){
    n=read();m=read();p=read();
    std::printf("%lld",exlucas());
    return 0;
}

礼物那题

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline LL read(){
    LL x=0,y=1;
    char c=std::getchar();
    while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
    return y?x:-x;
}
LL p;
inline LL power(LL a,LL b,LL pr){
    LL ret=1;
    while(b){
        if(b&1) ret=(ret*a)%pr;
        b>>=1;a=(a*a)%pr;
    }
    return ret;
}
void exgcd(LL a,LL b,LL &x,LL &y){
    if(!b) return x=1,y=0,void();
    exgcd(b,a%b,x,y);
    LL tmp=x;x=y;
    y=tmp-a/b*y;
}
inline LL getinv(LL nn,LL mod){
    LL x,y;
    exgcd(nn,mod,x,y);
    return (x+mod)%mod;
}
inline LL getfac(LL nn,LL pr,LL pp){//n!=x*p^y
    if(!nn) return 1;
    reg LL ans=1;
    for(reg LL i=2;i<pr;i++)
        if(i%pp) ans=ans*i%pr;
    ans=power(ans,nn/pr,pr);
    reg LL tmp=nn%pr;
    for(reg LL i=2;i<=tmp;i++)
        if(i%pp) ans=ans*i%pr;
    return ans*getfac(nn/pp,pr,pp)%pr;
}
inline LL C(LL nn,LL mm,LL pp,LL pr){
    LL x=getfac(nn,pr,pp),y=getfac(mm,pr,pp),z=getfac(nn-mm,pr,pp);
    LL num=0;//计算因数种有几个p
    for(reg LL i=nn;i;i/=pp) num+=i/pp;
    for(reg LL i=mm;i;i/=pp) num-=i/pp;
    for(reg LL i=nn-mm;i;i/=pp) num-=i/pp;
    return x*getinv(y,pr)%pr*getinv(z,pr)%pr*power(pp,num,pr)%pr;
}
inline void crt(LL &ans,LL pr,LL ai){
    ans=(ans+(getinv(p/pr,pr)*ai%p*(p/pr)%p))%p;//这里p/pr就相当于crt里的Mi 
}
inline LL exlucas(LL n,LL m){
    LL ans=0,pp=p,pr,sqrt=std::sqrt(p);//pr=p^r
    for(reg LL i=2;i<=sqrt;i++)if(!(pp%i)){
        pr=1;
        while(!(pp%i)) pp/=i,pr*=i;
        crt(ans,pr,C(n,m,i,pr));
    }
    if(pp>1) crt(ans,pp,C(n,m,pp,pp));//还有因数 
    return ans;
}
LL w[10];
int main(){
    p=read();LL n=read(),m=read();
    LL sum=0;
    for(reg int i=1;i<=m;i++) w[i]=read(),sum+=w[i];
    if(sum>n) return std::puts("Impossible"),0;
    LL ans=1;
    for(reg int i=1;i<=m;i++){
        ans=(ans*exlucas(n,w[i]))%p;
        n-=w[i];
    }
    std::printf("%lld",ans);
    return 0;
}