[BZOJ2142]礼物 - A-Failure的博客

题目

Description

一年一度的圣诞节快要来到了。每年的圣诞节小E都会收到许多礼物，当然他也会送出许多礼物。不同的人物在小E心目中的重要性不同，在小E心中分量越重的人，收到的礼物会越多。

小E从商店中购买了n件礼物，打算送给m个人，其中送给第i个人礼物数量为wi。请你帮忙计算出送礼物的方案数（两个方案被认为是不同的，当且仅当存在某个人在这两种方案中收到的礼物不同）。由于方案数可能会很大，你只需要输出模P后的结果。

Input

输入的第一行包含一个正整数P，表示模；

第二行包含两个整整数n和m，分别表示小E从商店购买的礼物数和接受礼物的人数；

以下m行每行仅包含一个正整数wi，表示小E要送给第i个人的礼物数量。

Output

若不存在可行方案，则输出“Impossible”，否则输出一个整数，表示模P后的方案数。

Sample Input

Sample Output

【样例说明】

下面是对样例1的说明。以“/”分割，“/”前后分别表示送给第一个人和第二个人的礼物编号。12种方案详情如下：

1/23 1/24 1/34

2/13 2/14 2/34

3/12 3/14 3/24

4/12 4/13 4/23

【数据规模和约定】

设$P=p1^{c1} \times p2^{c2} \times p3^{c3} \times … \times pt ^ {ct}$，pi为质数。

对于100%的数据，1≤n≤10^9，1≤m≤5，1≤pi^ci≤10^5。

题解

答案就是求$C_{n}^{w_1}\times C_{n-w_1}^{w_2}\times … \times C_{n-w_1-…-w_{m-1}}^{w_m}$

因为$P$的特殊性质所以要用扩展$Lucas$搞

第一次写真的是一头雾水……

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=1e5+5;
LL _P_,ans=1;
int n,m,tot,sum;
int w[6],P[MAX],_P[MAX];
int exgcd(int a,int b,int &x,int &y)
{
	if(!b) return x=1,y=0,a;
	int ans=exgcd(b,a%b,x,y),tt=x;
	return x=y,y=tt-1ll*a/b*y,ans;
}
int inv(int a,int b)
{
	int x,y;
	return exgcd(a,b,x,y),(x%b+b)%b;
}
int Pow(int a,int b,int mod)
{
	int ans=1;
	for(;b;b>>=1,a=1ll*a*a%mod)
	  if(b&1) ans=1ll*ans*a%mod;
	return ans;
}
int Cal(int n,int p,int pk)
{
	if(!n) return 1;
	int ans=1;
	for(int i=2;i<=pk;++i)
	  if(i%p) ans=1ll*ans*i%pk;
	ans=Pow(ans,n/pk,pk);
	for(int i=2,L=n%pk;i<=L;++i)
	  if(i%p) ans=1ll*ans*i%pk;
	return 1ll*ans*Cal(n/p,p,pk)%pk;
}
int C(int n,int m,int p,int pk)
{
	if(m>n) return 0;
	int _A=Cal(n,p,pk),_B=Cal(m,p,pk),_C=Cal(n-m,p,pk),k=0;
	LL _=_P_/pk;
	for(int i=n;i;i/=p)
	  k+=i/p;
	for(int i=m;i;i/=p)
	  k-=i/p;
	for(int i=n-m;i;i/=p)
	  k-=i/p;
	return 1ll*_A*inv(_B,pk)%pk*inv(_C,pk)%pk*Pow(p,k,pk)%pk*_%_P_*inv(_,pk)%_P_;
}
int main()
{
	scanf("%lld%d%d",&_P_,&n,&m);
	for(int i=1;i<=m;++i)
	  scanf("%d",&w[i]),sum+=w[i];
	if(sum>n) return printf("Impossible"),0;
	LL mod=_P_,Ans=0;
	for(LL i=2;i*i<=mod;++i)
	  if(mod%i==0)
	  {
	  	P[++tot]=i,_P[tot]=1;
	  	while(mod%i==0) mod/=i,_P[tot]*=i;
	  }
	if(mod>1) P[++tot]=_P[tot]=mod;
	for(int i=1;i<=m;n-=w[i++])
	  {
	  	for(int j=1;j<=tot;++j)
	  	  Ans=(Ans+C(n,w[i],P[j],_P[j]))%_P_;
	  	ans=ans*Ans%_P_,Ans=0;
	  }
	return printf("%lld",ans),0;
}

题目