题意:给定一个序列${a_i}$,在$K_{a_i}~1\leq i\leq n$任取一个点,将这n个点依次连接形成一个环,求问有多少种方式删边使得这张图不存在环.

数据范围:$1\leq n\leq 2e5$

题解:

首先,$K_n$的生成树个数是$n^{n-2}$,证明可以用矩阵树定理,或者考虑组合意义.

设F(x)是生成树个数函数的$EGF$,即$F(x)=\sum_{i=0}^{\infty}\frac{i^{i-2}}{i!}x^i$

考虑生成函数的乘法的意义,即$[x^nn!]F(x)^2$表示的其实是由两棵生成树序列构成的森林的种数.考虑到森林之间不带标号,于是真实种数是$[x^nn!]\frac{F(x)^2}{2!}$.设$G(x)$是生成森林的$EGF$,则:$G(x)=\sum_{i=0}^{\infty}\frac{F(x)^i}{i!}=e^{F(x)}$.

如果不考虑大环的情况,那么$ans=2^n\Pi_{i=1}^n[x^{a_i}a_i!]G(x)$

但是其实是有大环的情况的.考虑$t_n$表示n个点,其中1,n两个点不连通的情况.

有:$t_n=\sum_{i=0}^{n-2}f_{i+1}g_{n-i-1}C_{n-2}^{i}$,设${t_n}$的EGF是$T(x)$,有$T(x)=\int\int F(x)^{‘}G(x)^{‘}$

故答案即为$ans=2^n\Pi_{i=1}^n[x^{a_i}a_i!]G(x)-\Pi_{i=1}^{n}([x^{a_i}a_i!]G(x)-[x^{a_i}a_i!]T(x))$

使用多项式技术即可做到$O(nlogn)$,如果不使用EGF,也可以用二项卷积式得到一个$O(nlog^2n)$的分治NTT做法.

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef pair<int,int> pii;
#define cs const
#define re register

namespace IO{
template<typename T>inline void read(T &x){
x=0;ll f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x=x*f;
}
}
using namespace IO;

cs int mod=998244353,N=810000,inv2=mod+1>>1;
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(int a,int b){return a<b?a-b+mod:a-b;}
inline int mul(int a,int b){return (ll)a*b%mod;}
inline int quickpow(int a,int b,int res=1){
while(b){
if(b&1)res=mul(res,a);
a=mul(a,a);
b>>=1;
}
return res;
}

typedef vector<int> Poly;

inline void print(cs Poly &a,char c=' ',ostream &out=cout){
for(int re i=0;i<a.size();++i)out<<a[i]<<c;
}

int r[N],inv[N];
inline void NTT(Poly &A,int len,int typ){
for(int re i=0;i<len;++i)if(i<r[i])swap(A[i],A[r[i]]);
for(int re i=1;i<len;i<<=1){
int wn=quickpow(typ==-1?(mod+1)/3:3,(mod-1)/i/2);
for(int re j=0;j<len;j+=i<<1)
for(int re k=0,x,y,w=1;k<i;++k,w=mul(w,wn)){
x=A[j+k],y=mul(w,A[j+k+i]);
A[j+k]=add(x,y);
A[j+k+i]=dec(x,y);
}
}
if(typ==-1)for(int re i=0;i<len;++i)A[i]=mul(A[i],inv[len]);
}
inline void init_rev(int len){
for(int re i=0;i<len;++i)r[i]=r[i>>1]>>1|((i&1)*(len>>1));
}

inline Poly operator+(cs Poly &a,cs Poly &b){
Poly c=a;c.resize(max(a.size(),b.size()));
for(int re i=0;i<b.size();++i)c[i]=add(c[i],b[i]);
return c;
}

inline Poly operator-(cs Poly &a,cs Poly &b){
Poly c=a;c.resize(max(a.size(),b.size()));
for(int re i=0;i<b.size();++i)c[i]=dec(c[i],b[i]);
return c;
}

inline Poly operator*(Poly a,Poly b){
int n=a.size(),m=b.size(),l=1;
while(l<n+m-1)l<<=1;
init_rev(l);
a.resize(l),NTT(a,l,1);
b.resize(l),NTT(b,l,1);
for(int re i=0;i<l;++i)a[i]=mul(a[i],b[i]);
NTT(a,l,-1);
a.resize(n+m-1);
return a;
}

inline Poly operator*(Poly a,int b){
for(int re i=0;i<a.size();++i)a[i]=mul(a[i],b);
return a;
}

inline Poly Deriv(Poly a){
for(int re i=0;i+1<a.size();++i)a[i]=mul(a[i+1],i+1);
a.pop_back();
return a;
}

inline Poly Integ(Poly a){
a.push_back(0);
for(int re i=a.size()-1;i;--i)a[i]=mul(a[i-1],inv[i]);
a[0]=0;
return a;
}

inline Poly Inv(cs Poly &a,int lim){
Poly c,b(1,quickpow(a[0],mod-2));
for(int re l=4;(l>>2)<lim;l<<=1){
init_rev(l);
c=a,c.resize(l>>1);
c.resize(l),NTT(c,l,1);
b.resize(l),NTT(b,l,1);
for(int re i=0;i<l;++i)b[i]=mul(b[i],dec(2,mul(c[i],b[i])));
NTT(b,l,-1);
b.resize(l>>1);
}
b.resize(lim);
return b;
}
inline Poly Inv(cs Poly &a){return Inv(a,a.size());}

inline Poly Ln(Poly a,int lim){
a=Integ(Deriv(a)*Inv(a,lim));
a.resize(lim);
return a;
}
inline Poly Ln(cs Poly &a){return Ln(a,a.size());}

inline Poly Exp(cs Poly &a,int lim){
Poly c,b(1,1);int n=a.size();
for(int re i=2;(i>>1)<lim;i<<=1){
c=Ln(b,i);
for(int re j=0;j<i;++j)c[j]=dec(j<n?a[j]:0,c[j]);
c[0]=add(c[0],1);
b=b*c;
b.resize(i);
}
b.resize(lim);
return b;
}
inline Poly Exp(cs Poly &a){return Exp(a,a.size());}

cs int w4=quickpow(3,(mod-1)/4);
inline Poly Cos(cs Poly &a,int lim){
Poly c=a;c.resize(lim);
c=(Exp(c*w4)+Exp(c*(mod-w4)))*inv2;
return c;
}
inline Poly Cos(cs Poly &a){return Cos(a,a.size());}

inline Poly Sin(cs Poly &a,int lim){
Poly c=a;c.resize(lim);
c=(Exp(c*w4)-Exp(c*(mod-w4)))*mul(inv2,quickpow(w4,mod-2));
return c;
}
inline Poly Sin(cs Poly &a){return Sin(a,a.size());}

inline Poly Sqrt(cs Poly &a,int lim){
Poly c,d,b(1,1);
for(int re l=4;(l>>2)<lim;l<<=1){
init_rev(l);
c=a,c.resize(l>>1);
d=Inv(b,l>>1);
c.resize(l),NTT(c,l,1);
d.resize(l),NTT(d,l,1);
for(int re j=0;j<l;++j)c[j]=mul(c[j],d[j]);
NTT(c,l,-1);
b.resize(l>>1);
for(int re j=0;j<(l>>1);++j)b[j]=mul(add(c[j],b[j]),inv2);
}
b.resize(lim);
return b;
}
inline Poly Sqrt(cs Poly &a){return Sqrt(a,a.size());}

inline Poly Ksm(Poly a,int k,int lim){
a=Exp(Ln(a)*k);
a.resize(lim);
return a;
}
inline Poly Ksm(cs Poly &a,int k){return Ksm(a,k,a.size());}

inline Poly operator/(Poly a,Poly b){
int re len=1,deg=a.size()-b.size()+1;
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
while(len<=deg)len<<=1;
b=Inv(b,len);b.resize(deg);
a=a*b;a.resize(deg);
reverse(a.begin(),a.end());
return a;
}

inline Poly operator%(cs Poly &a,cs Poly &b){
Poly c=a-(a/b)*b;
c.resize(b.size()-1);
return c;
}
int frac[N+10],invf[N+10];
Poly dp1,dp2,dp3;
inline void init_inv(int n){
inv[0]=inv[1]=1;
for(int i=2;i<N;++i)inv[i]=mul(inv[mod%i],mod-mod/i);
frac[0] = 1;
for(int i=1;i<N;i++)
frac[i]=mul(frac[i-1],i);
invf[N-1]=quickpow(frac[N-1],mod-2);
for(int i=N-2;i>=0;i--)
invf[i]=mul(invf[i+1],(i+1));
dp1.push_back(0),dp1.push_back(1);
/*
dp1=i^(i-2)/frac(i)
*/
for(int i=2;i<n;i++)
dp1.push_back(mul(quickpow(i,i-2),invf[i]));
dp2=Exp(dp1);
// for(int i=0;i<=10;i++)
// cout<<dp2[i]<<" ";
dp3=Integ(Integ(Deriv(dp1)*Deriv(dp2)));
for(int i=0;i<n;i++){
dp1[i]=mul(dp1[i],frac[i]);
dp2[i]=mul(dp2[i],frac[i]);
dp3[i]=mul(dp3[i],frac[i]);}
}
Poly A;
int n;
vector<int> k;
ll ans=0;
signed main(){
init_inv(200000+1);
read(n);
k.reserve(n+1);
for(int i=1;i<=n;i++)
read(k[i]);
ans=1ll*quickpow(2,n);
ll ans2=1;
for(int i=1;i<=n;i++)
{
ans2=mul(ans2,dp2[k[i]]);
}
ll ans3=1;
for(int i=1;i<=n;i++)
{
ans3=mul(ans3,dec(dp2[k[i]],dp3[k[i]]));
}
cout<<dec(mul(ans,ans2),ans3);
return 0;
}