zcmimi's blog
查看原题

点击跳转

ans={n\choose w_1}\cdot {n-w_1\choose w_2}\cdot {n-w_1-w_2\choose w_3}\cdots {n-w_1-w_2-\dots -w_{m-1}\choose w_m}

套扩展卢卡斯即可

#include<bits/stdc++.h>
#define gc getchar()
#define fur(i,x,y) for(int i=x;i<=y;++i)
void in(int &x){x=0;char c;bool f=0;for(c=gc;c<'0'||'9'<c;c=gc)f^=c=='-';for(x=c-48,c=gc;'0'<=c&&c<='9';x=x*10+c-48,c=gc);if(f)x=-x;}
const int N=100011;
int P,lim,w[N],pi[N],pk[N],cnt;
int pw(int x,int b,int p){
    int res=1;
    while(b){
        if(b&1)res=1ll*res*x%p;
        b>>=1,x=1ll*x*x%p;
    }
    return res;
}
void exgcd(int a,int b,int&x,int&y){
    if(!b){x=1,y=0;return;}
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
int inv(int v,int p){
    int x,y;
    exgcd(v,p,x,y);
    return (x+=p)>p?x-p:x;
}
int crt(int v,int p){return 1ll*v*inv(P/p,p)%P*(P/p)%P;}
int fac(int n,int pi,int pk){
    if(!n)return 1;
    int res=1;
    fur(i,2,pk)
        if(i%pi)res=1ll*res*i%pk;
    res=pw(res,n/pk,pk);
    fur(i,2,n%pk)
        if(i%pi)res=1ll*res*i%pk;
    return 1ll*res*fac(n/pi,pi,pk)%pk;
}
int C(int n,int m,int pi,int pk){
    if(m>n)return 0;
    int cnt=0;
    for(int i=n;i;i/=pi)cnt+=i/pi;
    for(int i=m;i;i/=pi)cnt-=i/pi;
    for(int i=n-m;i;i/=pi)cnt-=i/pi;
    return 1ll*pw(pi,cnt,pk)*fac(n,pi,pk)%P
              *inv(fac(m,pi,pk),pk)%P*inv(fac(n-m,pi,pk),pk)%P;
}
int main(){
    int n,m,sum=0,t,ans=1,res;
    in(P),in(n),in(m),lim=sqrt(P);
    fur(i,1,m)in(w[i]),sum+=w[i];
    if(sum>n)return printf("Impossible"),0;
    t=P;
    fur(i,2,lim)if(t%i==0){
        pi[++cnt]=i;pk[cnt]=1;
        while(t%i==0)pk[cnt]*=i,t/=i;
    }
    if(t>1)pi[++cnt]=t,pk[cnt]=t;
    fur(i,1,m){
        res=0;
        fur(j,1,cnt)res=(res+crt(C(n,w[i],pi[j],pk[j]),pk[j]))%P;
        ans=1ll*ans*res%P;
        n-=w[i];
    }
    printf("%d\n",ans);
}
LG 2183 [国家集训队]礼物
comment评论
Search
search