bzoj 2142 礼物——扩展lucas模板

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

没给P的范围，但说 pi ^ ci<=1e5，一看就是扩展lucas。

学习材料：https://blog.csdn.net/clove_unique/article/details/54571216

　　　　　https://www.cnblogs.com/elpsycongroo/p/7620197.html

于是打(抄)了第一份exlucas的板子。那个把 pi的倍数 和 其余部分 分开处理的写法非常清楚！自己本来还想弄个pair的函数什么的。

num的范围？

#include<iostream>

#include<cstdio>

#include<cstring>

#define ll long long

using namespace std;

const int N=;

int num,m[N],pk[N];

ll mod,w[],a[N],x,y,ans,n,l;

void init(ll n)

{

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

    if(n%i==)

      {

    m[++num]=i;pk[num]=;

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

      }

  if(n>)m[++num]=n,pk[num]=n;

}

ll pw(ll x,ll k,int mod)

{

  ll ret=;x%=mod;while(k){if(k&)(ret*=x)%=mod;(x*=x)%=mod;k>>=;}return ret;

}

ll multi(ll n,int pi,int pk)

{

  if(!n)return ;//

  ll sum=;

  for(int i=;i<pk;i++)if(i%pi)(sum*=i)%=pk;

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

  for(int i=;i<=n%pk;i++)if(i%pi)(sum*=i)%=pk;

  return sum*multi(n/pi,pi,pk)%pk;//n/pi!!

}

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

{

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

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

}

ll inv(ll n,ll mod){exgcd(n,mod,x,y);return (x+mod)%mod;}

ll exlucas(ll n,ll m,int pi,int pk)

{

  if(n<m)return ;//

  ll a=multi(n,pi,pk),b=multi(m,pi,pk),c=multi(n-m,pi,pk);

  ll k=;

  for(ll i=n;i;i/=pi)k+=i/pi;//阶乘的pi的个数

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

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

  return a*inv(b,pk)%pk*inv(c,pk)%pk*pw(pi,k,pk)%pk;

}

ll crt()

{

  ll M=,ret=;for(int i=;i<=num;i++)M*=pk[i];//pk,not m(pi)

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

    {

      ll w=M/pk[i];

      (ret+=w*inv(w,pk[i])*a[i])%=mod;

    }

  return (ret+mod)%mod;

}

ll excomb(ll n,ll k)

{

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

    a[i]=exlucas(n,k,m[i],pk[i]);

  return crt();

}

int main()

{

  scanf("%lld%lld%lld",&mod,&n,&l);ll tmp=;

  init(mod);

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

  if(n<tmp){printf("Impossible");return ;}

  ans=;

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

    {

      tmp=excomb(n,w[i]);

      (ans*=tmp)%=mod;n-=w[i];

    }

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

  return ;

}