【国家集训队】礼物

Source and Judge

国家集训队
CF_R503_div1_A

Record

5h

Analysis

请先思考后再展开

拓展lucas裸题
直接算$\prod C_n^{wi} \% p$,但每次要减少n
时间复杂度$O(\sqrt N + plog_p n)$

调试了一天……好多细节

Code

请先思考后再展开
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
95
96
97
98
99
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
ll qpower(ll a,ll e,ll MOD)
{
ll ans=1;
while(e>0)
{
if(e&1) ans=ans*a%MOD;
a=a*a%MOD;e>>=1;
}
return ans;
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0) {x=1,y=0;return a;}
ll tx,ty;ll d=exgcd(b,a%b,tx,ty);
x=ty;y=tx-(a/b)*ty;
return d;
}
ll inv(ll a,ll MOD)
{
ll x,y;exgcd(a,MOD,x,y);
x=(x%MOD+MOD)%MOD;
return x;
}
ll fac(int n,ll p,ll MOD)
{
if(n<=0) return 1;
ll ans=1;
ll t=n/MOD;
for(int i=1;i<=MOD-1;i++) if((i%p)!=0) ans=ans*i%MOD;
//debug 这里不要调用一次fac,会导致重复计算剩下的
ans=qpower(ans,t,MOD);
for(int i=t*MOD+1;i<=n;i++) if((i%p)!=0) ans=ans*i%MOD;
return ans*fac(n/p,p,MOD)%MOD;//debug 忘记去除p后,还会有东西剩下来
}
ll smallC(ll m,ll n,ll p,ll MOD)
{
ll num=0;
for(ll pk=p;pk<=n;pk*=p) num+=n/pk;
for(ll pk=p;pk<=m;pk*=p) num-=m/pk;
for(ll pk=p;pk<=(n-m);pk*=p) num-=(n-m)/pk;
ll ans=qpower(p,num,MOD);//不互质的烦恼
ans=ans*fac(n,p,MOD)%MOD;
ans=ans*inv(fac(m,p,MOD),MOD)%MOD;
ans=ans*inv(fac(n-m,p,MOD),MOD)%MOD;
return ans;
}
ll C(ll m,ll n,ll MOD)//exLucas
{
ll ans=0;ll tmp=MOD;
for(int p=2;p*p<=tmp;p++)
{
int pk=1;
while(tmp%p==0) tmp/=p,pk*=p;
if(pk>1) (ans+=smallC(m,n,p,pk) *(MOD/pk)%MOD *inv(MOD/pk,pk) %MOD)%=MOD;//CRT
}
if(tmp>1) (ans+=smallC(m,n,tmp,tmp) *(MOD/tmp)%MOD *inv(MOD/tmp,tmp) %MOD)%=MOD;
return ans;
}
int w[10];
void main()
{
int MOD;scanf("%d",&MOD);
int n,m;scanf("%d%d",&n,&m);
ll tot=0;
for(int i=1;i<=m;i++) scanf("%d",&w[i]),tot+=w[i];
if(tot>n) puts("Impossible");
else
{
ll ans=1;
for(int i=1;i<=m;i++) ans=ans*C(w[i],n,MOD)%MOD,n-=w[i];
printf("%lld",ans);
}
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/1774.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%