「国家集训队」礼物

发表于 | 分类于 | | 浏览量： 次

模数不是大质数，怎么办啊。

传送门

洛谷P2183

BZOJ2142

题解

首先，比较显然的是，当且仅当$\sum_{i=1}^{m}{w_i}>n$时无解。

不妨设$w{m+1}=n-\sum{i=1}^{m}{w_i}$。

那么直接上公式，所以答案为

由于模数不是质数，所以直接将模数分解质因数，然后分别计算模每一项的值，然后用CRT搞到一起就行了，就是EXLUCS的流程。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<cstdio>
using namespace std;
typedef long long LL;
int pri[10000];LL sum,n,m,p,w[10];
inline void make_p()
{
	static bool vis[100005];
	vis[0]=vis[1]=true;
	for(int i=2;i<=100000;i++)
	{
		if(!vis[i]) pri[++pri[0]]=i;
		for(int j=1;j<=pri[0]&&pri[j]*i<=100000;j++)
		{
			vis[pri[j]*i]=true;
			if(i%pri[j]==0) break;
		}
	}
}
LL QP(LL a,LL b,LL TT)
{
	LL ret=1,w=a;
	while(b)
	{
		if(b&1) ret=ret*w%TT;
		w=w*w%TT;b>>=1;
	}
	return ret;
}
LL Exgcd(LL a,LL b,LL& x,LL& y)
{
	if(!b){x=1;y=0;return a;}
	LL d=Exgcd(b,a%b,x,y);
	LL t=x;x=y;y=t-a/b*y;
	return d;
}
LL inv(LL a,LL TT)
{
	LL X,Y,D=Exgcd(a,TT,X,Y);
	return (X%(TT/D)+(TT/D))%(TT/D);
}
LL Fac(LL n,LL p,LL pk)
{
	if(n==0) return 1;
	LL ret1=1,ret2=1;
	for(int i=1;i<=pk;i++)
	{
		if(i%p!=0) ret1=ret1*i%pk;
		if(i%p!=0&&i<=n%pk) ret2=ret2*i%pk;
	}
	ret1=QP(ret1,n/pk,pk);
	return Fac(n/p,p,pk)*ret1%pk*ret2%pk;
}
LL Count(LL n,LL p){LL ret=0;while(n){ret+=n/p;n/=p;}return ret;}
LL Calc(LL n,LL m,LL p,LL pk)
{
	LL cnt1=Count(n,p),cnt2=0,ret=Fac(n,p,pk);
	for(int i=1;i<=m;i++) cnt2+=Count(w[i],p);
	for(int i=1;i<=m;i++) ret=ret*inv(Fac(w[i],p,pk),pk)%pk;
	ret=ret*QP(p,cnt1-cnt2,pk)%pk;
	return ret;
}
LL ExLucas(LL n,LL m,LL TT)
{
	LL LCM=1,X=0,Y,Z,D;
	for(int i=1;i<=pri[0];i++)
	{
		if(TT%pri[i]==0)
		{
			LL pk=1;
			while(TT%pri[i]==0){pk*=pri[i];TT/=pri[i];}
			LL A=Calc(n,m,pri[i],pk);
			D=Exgcd(LCM,pk,Y,Z);
			Y*=(A-X)/D;
			X+=Y*LCM;
			LCM=LCM/D*pk;
		}
	}
	X=(X%LCM+LCM)%LCM;
	return X;
}
int main()
{
	make_p();
	scanf("%lld%lld%lld",&p,&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%lld",&w[i]);
		sum+=w[i];
	}
	if(sum>n){printf("Impossible\n");return 0;}
	w[++m]=n-sum;
	printf("%lld\n",ExLucas(n,m,p));
	return 0;
}