BZOJ - 2142 礼物 (扩展Lucas定理)

扩展Lucas定理模板题（貌似这玩意也只能出模板题了吧~~本菜鸡见识鄙薄，有待指正）

原理：

https://blog.csdn.net/hqddm1253679098/article/details/82897638

https://blog.csdn.net/clove_unique/article/details/54571216

感觉扩展Lucas定理和Lucas定理的复杂程度差了不止一个档次，用到了一大堆莫名其妙的函数。

另外谁能告诉我把一个很大的组合数对一个非质数取模有什么卵用

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const ll N=;

 ll c[N],m[N],p[N],k[N],n,nn,mm[N],kk,pp;

 void exgcd(ll a,ll b,ll& x,ll& y,ll& g) {//扩展欧几里得

     if(!b)x=,y=,g=a;

     else exgcd(b,a%b,y,x,g),y-=x*(a/b);

 }

 ll inv(ll a,ll b) {//逆元

     ll x,y,g;

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

     return x%b;

 }

 ll Pow(ll a,ll b,ll mod) {//快速幂

     ll ret=;

     for(; b; b>>=,a=a*a%mod)if(b&)ret=ret*a%mod;

     return ret;

 }

 ll fact(ll n,ll p,ll k) {//求n!去掉质因子p后对p^k取模的值

     if(n==)return ;

     ll mod=Pow(p,k,),ret=,cnt=n/mod;

     for(ll i=; i<=mod; ++i)if(i%p)ret=ret*i%mod;

     ret=Pow(ret,cnt,mod);

     for(ll i=n-cnt*mod; i>=; --i)if(i%p)ret=ret*i%mod;

     return ret*fact(n/p,p,k)%mod;

 }

 ll C(ll n,ll m,ll p,ll k) {//求C(n,m)对p^k取模的值

     ll mod=Pow(p,k,);

     ll ret=fact(n,p,k)*inv(fact(m,p,k),mod)%mod*inv(fact(n-m,p,k),mod)%mod;

     ll cnt=;

     for(ll i=p; i<=n; i*=p)cnt+=n/i;

     for(ll i=p; i<=m; i*=p)cnt-=m/i;

     for(ll i=p; i<=n-m; i*=p)cnt-=(n-m)/i;

     if(cnt<)ret=ret*inv(Pow(p,-cnt,mod),mod)%mod;

     else ret=ret*Pow(p,cnt,mod)%mod;

     return ret;

 }

 ll CRT(ll* c,ll* m,ll n) {//扩展中国剩余定理

     ll M=,C=,x,y,g;

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

         exgcd(M,m[i],x,y,g);

         if((c[i]-C)%g)return -;

         C=x%(m[i]/g)*((c[i]-C)/g)%(m[i]/g)*M+C;

         M=M*m[i]/g,C%=M;

     }

     return (C%M+M)%M;

 }

 void split(ll x) {//唯一分解定理

     n=;

     for(ll i=; i*i<=x; ++i)if(x%i==) {

             p[n]=i,k[n]=;

             while(x%i==)x/=i,k[n]++;

             n++;

         }

     if(x>)p[n]=x,k[n++]=;

 }

 ll C(ll nn,ll mm,ll P) {//计算C(nn,mm)%P

     split(P);

     for(ll i=; i<n; ++i)m[i]=Pow(p[i],k[i],),c[i]=C(nn,mm,p[i],k[i]);

     return CRT(c,m,n);

 }

 ll solve() {

     if(accumulate(mm,mm+kk,0ll)>nn)return -;

     ll ret=;

     for(ll i=; i<kk; ++i)ret=ret*C(nn,mm[i],pp)%pp,nn-=mm[i];

     return ret;

 }

 int main() {

     while(scanf("%lld",&pp)==) {

         scanf("%lld%lld",&nn,&kk);

         for(ll i=; i<kk; ++i)scanf("%lld",&mm[i]);

         ll ans=solve();

         if(!~ans)printf("Impossible\n");

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

     }

     return ;

 }