0%

BZOJ3684 题解 - 大朋友和多叉树

$\color{white}\colorbox{black}{黑暗的题目链接}$

显然有

可以发现这里有一个恶心的多项式复合($x^i\rightarrow F^i(x)$),幸运的是 $F(x)$ 的逆非常好求

那么拉格朗日反演即可。

顺带一提这个质数的原根是 7。

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
100
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int p=950009857,maxN=262144,g=7,ig=135715694,inv2=(p+1)/2;
int W[maxN],iW[maxN];
int fac[maxN],ifac[maxN],inv[maxN];
int qpow(int a,int k){
int ans=1;
while(k){
if(k&1) ans=1LL*ans*a%p;
a=1LL*a*a%p;
k>>=1;
}
return ans;
}
void init(){
int w=qpow(g,(p-1)/maxN),iw=qpow(ig,(p-1)/maxN);
W[0]=iW[0]=1;
for(int i=1;i<maxN;i++)
W[i]=1LL*W[i-1]*w%p,
iW[i]=1LL*iW[i-1]*iw%p;
fac[0]=ifac[0]=fac[1]=ifac[1]=inv[1]=1;
for(int i=2;i<maxN;i++)
fac[i]=1LL*fac[i-1]*i%p,
inv[i]=1LL*(p-p/i)*inv[p%i]%p,
ifac[i]=1LL*ifac[i-1]*inv[i]%p;
}
int R[maxN];
void NTT(int d[],bool flg,int n0){
int x=1,len=0;while(x<n0) x<<=1,len++;
for(int i=0;i<x;i++){
R[i]=(R[i>>1]>>1)|((i&1)<<(len-1));
if(i<R[i]) swap(d[i],d[R[i]]);
}
for(int i=1,l=maxN/(i<<1);i<x;i<<=1,l>>=1)
for(int j=0;j<x;j+=(i<<1))
for(int k=0,u=0;k<i;k++,u+=l){
int a0=d[j|k],a1=1LL*(flg?iW[u]:W[u])*d[j|i|k]%p;
d[j|k]=(a0+a1)%p;d[j|i|k]=a0-a1+p;
if(d[j|i|k]>=p)d[j|i|k]-=p;
}
if(flg){
int invx=qpow(x,p-2);
for(int i=0;i<x;i++) d[i]=1LL*d[i]*invx%p;
}
}

int tmpans[maxN+5],tmpd[maxN+5];
void Inv(int d[],int ans[],int n0){
if(n0==1){ans[0]=qpow(d[0],p-2);return;}
Inv(d,ans,n0>>1);
for(int i=0;i<n0;i++) tmpans[i]=ans[i],tmpd[i]=d[i];
NTT(tmpans,0,n0<<1);NTT(tmpd,0,n0<<1);
for(int i=0;i<(n0<<1);i++) tmpans[i]=1LL*tmpans[i]*tmpans[i]%p*tmpd[i]%p;
NTT(tmpans,1,n0<<1);
for(int i=0;i<n0;i++) ans[i]=((ll)ans[i]+ans[i]-tmpans[i]+p)%p;
for(int i=0;i<(n0<<1);i++) tmpans[i]=tmpd[i]=0;
}
void Der(int d[],int ans[],int n0){
for(int i=0;i<n0;i++) ans[i]=1LL*d[i+1]*(i+1)%p;
}
void Int(int d[],int ans[],int n0){
for(int i=n0-1;i>=0;i--) ans[i+1]=1LL*d[i]*inv[i+1]%p;ans[0]=0;
}
int derd[maxN+5],invd[maxN+5];
void Ln(int d[],int ans[],int n0){
Der(d,derd,n0);Inv(d,invd,n0);
NTT(derd,0,n0<<1);NTT(invd,0,n0<<1);
for(int i=0;i<(n0<<1);i++) derd[i]=1LL*derd[i]*invd[i]%p;
NTT(derd,1,n0<<1);Int(derd,ans,n0);
for(int i=0;i<(n0<<1);i++) derd[i]=invd[i]=0;
}
int lnans[maxN+5];
void Exp(int d[],int ans[],int n0){
if(n0==1){ans[0]=1;return;}
Exp(d,ans,n0>>1);
Ln(ans,lnans,n0);
for(int i=0;i<n0;i++) lnans[i]=(d[i]-lnans[i]+p)%p;
lnans[0]=(lnans[0]+1)%p;
NTT(lnans,0,n0<<1);NTT(ans,0,n0<<1);
for(int i=0;i<(n0<<1);i++) ans[i]=1LL*ans[i]*lnans[i]%p;
NTT(ans,1,n0<<1);
for(int i=0;i<n0;i++) lnans[i]=0;
for(int i=n0;i<(n0<<1);i++) ans[i]=lnans[i]=0;
}

int N,T;
int G[maxN],ANS[maxN];

int main(){
init();
scanf("%d%d",&N,&T);
G[0]=1;
while(T--){int x;scanf("%d",&x);G[x-1]=p-1;}
int N0=1;while(N0<=N) N0<<=1;
Ln(G,G,N0);for(int i=0;i<N0;i++) G[i]=(p-1LL*G[i]*N%p)%p;
Exp(G,ANS,N0);
printf("%d\n",1LL*ANS[N-1]*inv[N]%p);
}