P2183 [国家集训队]礼物

文章目录

R e s u l t Result Result

---

H y p e r l i n k Hyperlink Hyperlink

https://www.luogu.com.cn/problem/P2183

---

D e s c r i p t i o n Description Description

有 n n n件礼物，要送给 m m m个人，第 i i i个人要收到 a i a_i ai​的礼物，答案对 p p p取模
求方案数

数据范围： n ≤ 1 0 9 , m ≤ 5 , p , a i ≤ 1 0 9 n\leq 10^9,m\leq 5,p,a_i\leq 10^9 n≤109,m≤5,p,ai​≤109

---

S o l u t i o n Solution Solution

考虑到 m m m很小，我们模拟礼物一件一件送的过程
我们从 n n n个礼物中挑选出 a 1 a_1 a1​件送给1
从 n − a 1 n-a_1 n−a1​个礼物中挑选出 a 2 a_2 a2​件送给2
从 n − a 1 − a 2 n-a_1-a_2 n−a1​−a2​个礼物中挑选出 a 3 a_3 a3​件送给3
以此类推
则方案数为 ∏ i = 1 m C n − ∑ j = 1 j < i a i a i \prod_{i=1}^m C_{n-\sum^{j<i}_{j=1} a_i}^{a_i} ∏i=1m​Cn−∑j=1j<i​ai​ai​​
由于模数不一定是质数，用扩展卢卡斯定理即可
当然你也可以用组合的思想把式子展开合并最后得到一堆阶乘相乘的形式
时间复杂度： O ( m ( p l o g p n ) ) O(m(plog_pn)) O(m(plogp​n))

---

C o d e Code Code

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;LL p,n,m,sum,a[6],res,now;
inline LL read()
{
	char c;LL d=1,f=0;
	while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;
	while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;
	return d*f;
}
inline LL ksm(LL x,LL y,LL p)
{
	LL res=1;
	for(;y;y>>=1,(x*=x)%=p) if(y&1) (res*=x)%=p;
	return res;
}
inline void Exgcd(LL a,LL b,LL &x,LL &y)
{
	if(b==0) return (void)(x=1,y=0);
	Exgcd(b,a%b,x,y);LL tmp=x;x=y;y=tmp-a/b*y;return;
}
inline LL INV(LL a,LL p)
{
	LL x,y;
 	Exgcd(a,p,x,y);
 	return (x+p)%p;
}
inline LL Fac(LL n,LL p,LL pk) 
{
	if(n<2) return 1;
	LL prod_xh=1,prod_last=1;
	for(LL i=1;i<=pk;i++) if(i%p) (prod_xh*=i)%=pk;
	prod_xh=ksm(prod_xh,n/pk,pk);
	for(LL i=pk*(n/pk);i<=n;i++) if(i%p) (prod_last*=i%pk)%=pk;
	return Fac(n/p,p,pk)*prod_xh%pk*prod_last%pk;
}
inline LL G(LL n,LL p)
{
	if(n<p) return 0;
	return G(n/p,p)+(n/p);
}
inline LL C(LL n,LL m,LL p,LL pk){return Fac(n,p,pk)*INV(Fac(m,p,pk),pk)%pk*INV(Fac(n-m,p,pk),pk)%pk*ksm(p,G(n,p)-G(m,p)-G(n-m,p),pk)%pk;}
LL A[65],B[65],tot;
inline LL Exlucas(LL n,LL m,LL p)
{
	LL x=p;tot=0;
	for(LL i=2;i*i<=x;i++)
	if(x%i==0)
	{
		LL tmp=1;
		do{x/=i;tmp*=i;}while(x%i==0);
		B[++tot]=C(n,m,i,tmp);A[tot]=tmp;
	}
	if(x!=1){B[++tot]=C(n,m,x,x);A[tot]=x;}
	LL res=0,M=p;
	for(register int i=1;i<=tot;i++)
	{
		LL Mi=M/A[i],Mi_=INV(Mi,A[i]);
		(res+=B[i]*Mi%M*Mi_%M)%=M;
	}
	return res;
}
signed main()
{
	p=read();n=read();m=read();
	for(register int i=1;i<=m;i++) a[i]=read(),sum+=a[i];
	if(n<sum) return puts("Impossible")&0;
	res=1;
	for(register int i=1;i<=m;i++)
	{
		(res*=Exlucas(n,a[i],p))%=p;
		n-=a[i];
	}
	printf("%lld",res);
}