[文章目录]
Description
一年一度的圣诞节快要来到了。每年的圣诞节小E都会收到许多礼物，当然他也会送出许多礼物。不同的人物在小E心目中的重要性不同，在小E心中分量越重的人，收到的礼物会越多。小E从商店中购买了n件礼物，打算送给m个人，其中送给第i个人礼物数量为wi。请你帮忙计算出送礼物的方案数（两个方案被认为是不同的，当且仅当存在某个人在这两种方案中收到的礼物不同）。由于方案数可能会很大，你只需要输出模P后的结果。P=p1^c1 * p2^c2 * p3^c3 * … *pt ^ ct，pi为质数。1≤n≤109，1≤m≤5，1≤pi^ci≤10^5。
扩展lucas。答案不就是一堆组合数乘一起吗？？？咋求啊。。。。
将mod分解质因数，求出答案对于每一个p^c的余数，然后用中国剩余定理（CRT）合并就好了。
一个组合数模一个质数的c次幂怎么求？？？快速阶乘，将p因子单独考虑。然后扩展gcd求关于 mod p^c的逆元。显然gcd为1，存在逆元。
神Impossible？？？居然忘特判了。。。
所以说路还很长啊。。。
学习了快速阶乘 O(mod) 扩展gcd求逆元？？？ 中国剩余定理
行吧，this is 扩展lucas
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(ll &x)
{
x=0; char ch=getchar(); ll re=1;
while(ch<'0'||ch>'9') {if(ch=='-') re=-1; ch=getchar();}
while(ch>='0'&&ch<='9')
x=(x<<1)+(x<<3)+ch-'0',ch=getchar(); x*=re;
}
ll mod,n,m,w[10],jc[101000],sum;
inline ll Pow(ll x,ll y,ll P)
{
ll re=1;
for(;y;y>>=1,x=x*x%P) if(y&1) re=re*x%P;
return re;
}
void extgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
if(b==0) d=a,x=1,y=0;
else extgcd(b,a%b,d,y,x),y-=a/b*x;
}
inline ll Inv(ll a,ll b)
{
ll d,x,y;
extgcd(a,b,d,x,y);
return d==1?(x%b+b)%b:-1;
}
ll Fac(ll x,ll p,ll pr)
{
if(!x) return 1;
return Pow(jc[pr],x/pr,pr)*jc[x%pr]%pr*Fac(x/p,p,pr)%pr;
}
inline ll C(ll x,ll y,ll p,ll pr)
{
if(x<y) return 0; ll re=0;
for(ll i=x;i;i/=p) re+=i/p;
for(ll i=y;i;i/=p) re-=i/p;
for(ll i=x-y;i;i/=p) re-=i/p;
re=Pow(p,re,pr);
if(!re) return 0; jc[0]=1;
for(ll i=1;i<=pr;++i) jc[i]=((i%p)?jc[i-1]*i%pr:jc[i-1]);
return re*Fac(x,p,pr)%pr*Inv(Fac(y,p,pr),pr)%pr*Inv(Fac(x-y,p,pr),pr)%pr;
}
ll modp[101000],modpr[101000],cnt,ans=1;
ll crt(ll x,ll y)
{
ll re=0;
for(int i=1;i<=cnt;++i)
re=(re+mod/modpr[i]*Inv(mod/modpr[i],modpr[i])%mod*C(x,y,modp[i],modpr[i])%mod)%mod;
return re;
}
int main()
{
read(mod); read(n); read(m);
for(int i=1;i<=m;++i) read(w[i]),sum+=w[i];
if(sum>n){puts("Impossible");return 0;} ll c=mod;
for(ll i=2;i*i<=c;++i)
if(c%i==0)
{
modp[++cnt]=i; modpr[cnt]=1;
while(c%i==0) c/=i,modpr[cnt]*=i;
}
if(c!=1) modp[++cnt]=c,modpr[cnt]=c;
for(int i=1;i<=m;++i)
{
ans=ans*crt(n,w[i])%mod;
n-=w[i];
}
printf("%lld",ans);
return 0;
}