题解 P2183 【[国家集训队]礼物】
VenusM1nT
2019-08-26 21:31:39
扩展卢卡斯。
这题相当简单啊……唯一的难度就是在 $\texttt{ExLucas}$ 上了吧……
我们需要将 $\text{sum}$ 个礼物分给 $n$ 个人，每个人需要拿的礼物数为 $a_i$，由于每个礼物不同，要求方案数，容易想到组合数学。
我们考虑一道小学奥数题：$7$ 个人中选 $3$ 个拍照，方案数是 $7\times 6\times 5$，而它的具体意义是：考虑第一个位置能选谁，方案数是 $7$，再考虑第二个位置，由于第一个位置已经放了一个人，所以方案数是 $6$，同理，第三个位置方案数为 $5$，然后我们再使用乘法原理将它们合并。同理，我们对这道题使用相同的思想进行拆解，考虑第一个人选礼物的方案数，是 $n$ 个里选 $a_1$ 个，即 $\binom{n}{a_1}$，再考虑第二个，此时我们还剩下 $n-a_1$ 个礼物，选 $a_2$ 个，方案数为 $\binom{n-a_1}{a_2}$，以此类推，第三个的方案数为 $\binom{n-a_1-a_2}{a_3}$。至此，我们已经得出了此题的做法。
令
$$\text{sum}_i=\sum_{j=1}^{i}a_i$$
则答案为
$$\text{ans}=\prod_{i=1}^{m}\binom{n-\text{sum}_ {i-1}}{a_i}\ \text{mod}\ p$$
使用 $\texttt{ExLucas}$ 即可解出。
```cpp
#include<bits/stdc++.h>
#define MAXN 15
#define reg register
#define inl inline
#define int long long
using namespace std;
template <typename T> inl void Read(reg T &x)
{
x=0;
reg int fu=1;
reg char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') fu=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch-48);
x*=fu;
}
void ExGcd(reg int a,reg int b,reg int &x,reg int &y)
{
if(!b)
{
x=1;
y=0;
return;
}
ExGcd(b,a%b,x,y);
reg int t=x;
x=y;
y=t-a/b*y;
}
int Gcd(reg int x,reg int y)
{
return !y?x:Gcd(y,x%y);
}
inl int Inv(reg int a,reg int b)
{
reg int x,y;
ExGcd(a,b,x,y);
return (x%b+b)%b;
}
inl int Pow(reg int x,reg int y,reg int p)
{
reg int res=1;
for(;y;y>>=1,x=x*x%p) if(y&1) res=res*x%p;
return res;
}
inl int Crt(reg int x,reg int y,reg int p)
{
return Inv(y/p,p)*(y/p)*x;
}
int Fac(reg int x,reg int a,reg int p)
{
if(!x) return 1;
reg int res=1;
for(reg int i=1;i<=p;i++) if(i%a) res=res*i%p;
res=Pow(res,x/p,p);
for(reg int i=1;i<=x%p;i++) if(i%a) res=res*i%p;
return res*Fac(x/a,a,p)%p;
}
inl int C(reg int n,reg int m,reg int a,reg int p)
{
reg int x=Fac(n,a,p),y=Fac(m,a,p),z=Fac(n-m,a,p),sum=0;
for(reg int i=n;i>=1;i/=a) sum+=i/a;
for(reg int i=m;i>=1;i/=a) sum-=i/a;
for(reg int i=n-m;i>=1;i/=a) sum-=i/a;
return x*Pow(a,sum,p)%p*Inv(y,p)%p*Inv(z,p)%p;
}
inl int ExLucas(reg int n,reg int m,reg int p)
{
if(n<m) return 0;
reg int t=p,res=0;
for(reg int i=2;i*i<=p;i++)
{
reg int x=1;
while(!(t%i))
{
x*=i;
t/=i;
}
res=(res+Crt(C(n,m,i,x),p,x))%p;
}
if(t>1) res=(res+Crt(C(n,m,t,t),p,t))%p;
return res%p;
}
int n,m,p,a[MAXN],sum[MAXN],ans=1;
signed main()
{
reg int sm=0;
Read(p);
Read(n);
Read(m);
for(reg int i=1;i<=m;i++)
{
Read(a[i]);
sm+=a[i];
sum[i]=sum[i-1]+a[i];
}
if(sm>n) return puts("Impossible"),0;
for(reg int i=1;i<=m;i++) ans=ans*ExLucas(n-sum[i-1],a[i],p)%p;
printf("%lld\n",ans);
return 0;
}
```