bzoj2142 礼物——扩展卢卡斯定理

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2142

前几天学了扩展卢卡斯定理，今天来磕模板！

这道题式子挺好推的(连我都自己推出来了) ，总之就是在 n 个里取 w[1] 个，剩下的里面再取 w[2] 个，再在剩下的里面取...

这里的模数 P 一看就不是质数啊！大组合数对合数取模，就要用到扩展卢卡斯定理了；

关于扩展卢卡斯定理，可以看这篇博客：https://blog.csdn.net/clove_unique/article/details/54571216

然后模仿这篇博客写的(感觉挺清晰的)：https://www.cnblogs.com/elpsycongroo/p/7620197.html

扩展卢卡斯定理也没有想象中的那么难写嘛！

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

int const maxn=1e5+;

ll mod,n,m,w[],sum,p[maxn],pk[maxn],cnt,r[maxn],x,y;

void divide(ll n)

{

    for(ll i=;i*i<=n;i++)

        if(n%i==)

        {

            p[++cnt]=i; pk[cnt]=;

            while(n%i==)pk[cnt]*=i,n/=i;

        }

    if(n>)p[++cnt]=n,pk[cnt]=n;

}

ll pw(ll a,ll b,ll pk)

{

    ll ret=;

    for(;b;b>>=1ll,a=(a*a)%pk)

        if(b&)ret=(ret*a)%pk;

    return ret;

}

void exgcd(ll a,ll b,ll &x,ll &y)

{

    if(!b){x=; y=; return;}

    exgcd(b,a%b,x,y);

    ll t=x; x=y; y=(t-a/b*y)%mod;

}

ll inv(ll n,ll pk)

{

    exgcd(n,pk,x,y); return (x%pk+pk)%pk;

}

ll fac(ll n,ll p,ll pk)// n! mod pk=p^k 且去掉 p

{

    if(!n)return ;

    ll ret=;

    for(int i=;i<=pk;i++) if(i%p) ret=(ret*i)%pk;//一个循环节

    ret=pw(ret,n/pk,pk);

    for(int i=;i<=n%pk;i++) if(i%p) ret=(ret*i)%pk;

    return (ret*fac(n/p,p,pk))%pk;//递归求剩余部分

}

ll exlucas(ll n,ll m,ll p,ll pk)// C(n,m) mod pk=p^k

{

    if(n<m)return ;

    ll a=fac(n,p,pk),b=fac(m,p,pk),c=fac(n-m,p,pk);

    ll k=;//p的指数

    for(ll i=n;i;i/=p)k+=i/p;

    for(ll i=m;i;i/=p)k-=i/p;

    for(ll i=n-m;i;i/=p)k-=i/p;

    return (((a*inv(b,pk))%pk*inv(c,pk))%pk*pw(p,k,pk))%pk;//a*p^k/(b*c)

}

ll CRT()//合并模数

{

    ll M=,ret=;

    for(int i=;i<=cnt;i++)M*=pk[i];//pk而不是p !!!

    for(int i=;i<=cnt;i++)

    {

        ll w=M/pk[i];

        ret=(ret+w*inv(w,pk[i])*r[i])%M;

    }

    return (ret%M+M)%M;//

}

ll exc(ll n,ll m)// C(n,m)

{

    if(n<m)return ;

    for(int i=;i<=cnt;i++)

        r[i]=exlucas(n,m,p[i],pk[i]);

    return CRT();

}

int main()

{

    scanf("%lld%lld%lld",&mod,&n,&m);

    for(int i=;i<=m;i++)scanf("%lld",&w[i]),sum+=w[i];

    if(sum>n){printf("Impossible\n"); return ;}

    divide(mod);

    ll ans=;

    for(int i=;i<=m;i++)

    {

        ans=(ans*exc(n,w[i]))%mod;

        n-=w[i];

    }

    printf("%lld\n",ans);

    return ;

}