Luogu2183 礼物

Description

link

给 (m) 个人发 (n) 个礼物，不要求全部发完

每个人的礼物要求数量 (w_i)

求方案数，对大数取模（不是大质数）

(mle 5 nle10^9)

Solution

首先把答案写出来

[prod^{m}_ {i=1} inom{w_i}{n-sumlimits_{j=1}^{i-1} w_j} ]

考虑到 (m) 很小，所以我们可以暴力求

但是这个 (P) 比较大，没法直接做

其实可以换一发，把模数拆掉，然后上中国剩余定理来合并

比如 $P=prodlimits^{m} _ {i=1} p_i^{c_i} $

然后对于每个 (p_i) 求答案，然后上中国剩余定理合并

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
	inline int read()
	{
		int res=0,f=1; char k;
		while(!isdigit(k=getchar())) if(k=='-') f=-1;
		while(isdigit(k)) res=res*10+k-'0',k=getchar();
		return res*f;
	}
	inline int ksm(int x,int y,int mod)
	{
		x%=mod;
		int res=1; for(;y;y>>=1,(x*=x)%=mod) if(y&1) (res*=x)%=mod;
		return res;
	}
	inline void exgcd(int a,int b,int &x,int &y)
	{
		if(!b){x=1; y=0; return ;}
		exgcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*x;
		return ;
	}
	inline int inv(int a,int mod)
	{
		int x,y; exgcd(a,mod,x,y); 
		return (x%mod+mod)%mod;
	}
	int p,ans=1,a[101],sum=0,n,m;
	inline int fac(int n,int now,int pk)
	{
		if(!n) return 1; int ans=1; 
		for(int i=2;i<pk;++i) if(i%now) (ans*=i)%=pk;
		ans=ksm(ans,n/pk,pk);
		for(int i=2;i<=n%pk;++i) if(i%now) (ans*=i)%=pk;
		return ans*fac(n/now,now,pk)%pk;
	}
	inline int L(int n,int m,int now,int pk)
	{
		int s=0; for(int i=n;i;i/=now) s+=i/now;
		for(int i=m;i;i/=now) s-=i/now;
		for(int i=n-m;i;i/=now) s-=i/now;
		int a=fac(n,now,pk),b=fac(m,now,pk),c=fac(n-m,now,pk);
		return a*inv(b,pk)%pk*inv(c,pk)%pk*ksm(now,s,pk)%pk;
	}
	inline int C(int n,int m)
	{
		int res=0,t=p;
		for(int i=2;i*i<=t;++i)
		{
			if(t%i!=0) continue;
			int pk=1; while(t%i==0) pk*=i,t/=i;
			(res+=L(n,m,i,pk)*inv(p/pk,pk)%p*p/pk%p)%=p;
		}
		if(t>1) res+=L(n,m,t,t)*inv(p/t,t)%p*p/t%p,res%=p;
		return res;
	}
	signed main()
	{
		p=read(),n=read(),m=read();
		for(int i=1;i<=m;++i) a[i]=read(),sum+=a[i];
		if(sum>n) return puts("Impossible"),0;
		for(int i=1;i<=m;++i) ans*=C(n,a[i]),ans%=p,n-=a[i];
		printf("%lld
",ans);
		return 0;
	}
}
signed main(){return yspm::main();}