Description：

在一个 $s$ 个点的图 $s-n$ 条边使图中形成了 $n$ 个连通块，第 $i$ 个连通块中有 $a_i$ 个点。再连 $n-1$ 条边，使该图变成一棵树。对一种连边方案，设原图中第 $i$ 个连通块连出了 $d_i$ 条边，那么这棵树 $T$ 的价值为： $$ \mathrm{val}(T) = \left(\prod_{i=1}^{n} {d_i}^m\right)\left(\sum_{i=1}^{n} {d_i}^m\right) $$ 求出所有可能的生成树的价值之和，对 $998244353$ 取模。

$1\leqslant n\leqslant 30000$

Solution：

直接不考虑连通块，把原问题转换成 $n$ 个点连成一棵生成树，那么式子也就相应要变成： $$ val(T)=\prod_{i=1}^na_i^{d_i}d_i^m\sum_{i=1}^nd_i^m $$ 考虑到度数和 $prufer$ 序列的关系，我们可以思考能不能用 $prufer$ 序列来解决这个问题，因为枚举 $prufer$ 序列相当于枚举树，我们可以列出如下式子： $$ \begin{align} ans&=\sum_{d_1+d_2+\cdots d_k=n-2}\binom{n-2}{d_1,d_2,\dots,d_k}\prod_{i=1}^na_i^{d_i+1}(d_i+1)^m\sum_{i=1}^n(d_i+1)^m\\ &=(n-2)!\prod_{i=1}^na_i\sum_{d_1+d_2+\cdots d_n=n-2}\prod_{i=1}^n\frac{a_i^{d_i}}{d_i!}(d_i+1)^m\sum_{i=1}^n(d_i+1)^m \end{align} $$ 前面是一个常量不用管： $$ \begin{align} &\sum_{d_1+d_2+\cdots d_n=n-2}\bigg(\prod_{i=1}^n\frac{a_i^{d_i}}{d_i!}(d_i+1)^m\bigg)\bigg(\sum_{i=1}^n(d_i+1)^m\bigg)\\ =&\sum_{d_1+d_2+\cdots d_n=n-2}\bigg(\sum_{i=1}^n\frac{a_i^{d_i}}{d_i!}(d_i+1)^{2m}\prod_{j=1,i\ne j}^n\frac{a_i^{d_i}}{d_i!}(d_j+1)^m\bigg)\\ \end{align} $$ 构造两个生成函数： $$ \begin{align} A(x)&=\sum_{i\geqslant 0}\frac{(i+1)^{2m}}{i!}x^i\\ B(x)&=\sum_{i\geqslant 0}\frac{(i+1)^m}{i!}x^i \end{align} $$ 那么： $$ ans=[x^{n-2}]\sum_{i=1}^nA(a_ix)\prod_{j=1,j\ne i}^nB(a_jx) $$ 这一步转化真是妙啊，思考一下指数会发现刚好成立。

那么： $$ ans=[x^{n-2}]\sum_{i=1}^n\frac{A(a_ix)}{B(a_ix)}\prod_{j=1}^nB(a_jx)=[x^{n-2}]\bigg(\sum_{i=1}^n\frac{A(a_ix)}{B(a_ix)}\bigg)\times\bigg(\exp\sum_{i=1}^n\ln B(a_ix)\bigg) $$ 先考虑这个怎么做，可以把 $\frac{A(x)}{B(x)}$ 和 $\ln B(x)$ 求出来后把 $a_ix$ 代入再求和，把式子展开一下就会发现其实是要求一个： $$ \forall j\in[1,n]计算s_i=\sum_{j=1}^na_j^i $$ 这个直接套用 luogu4705玩游戏 那题的做法就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 120010

int a[MAXN];

int rev[MAXN];

int ww[MAXN << 1],*g = ww + MAXN;

#define P 998244353

int power(int a,int b)

{

	int res = 1;

	for(;b > 0;b = b >> 1,a = 1ll * a * a % P)if(b & 1)res = 1ll * res * a % P;

	return res;

}

int inver(int a){return power(a,P - 2);}

int init(int n)

{

	int l = 0,len = 1;

	for(;len <= n;len = len << 1)++l;

	for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	g[0] = g[-len] = 1;g[1] = g[1 - len] = power(3,(P - 1) / len);

	for(int i = 2;i < len;++i)g[i] = g[i - len] = 1ll * g[i - 1] * g[1] % P;

	return len;

}

void NTT(int f[],int l,int type)

{

	for(int i = 0;i < l;++i)

	{

		if(i < rev[i])swap(f[i],f[rev[i]]);

	}

	for(int i = 2;i <= l;i = i << 1)

	{

		int wn = g[type * l / i];

		for(int j = 0;j < l;j += i)

		{

			int w = 1;

			for(int k = j;k < j + i / 2;++k)

			{

				int u = f[k],t = 1ll * w * f[k + i / 2] % P;

				f[k] = (u + t) % P;

				f[k + i / 2] = (u - t + P) % P;

				w = 1ll * w * wn % P;

			}

		}

	}

	if(type == -1)

	{

		int ni = power(l,P - 2);

		for(int i = 0;i < l;++i)f[i] = 1ll * f[i] * ni % P;

	}

	return;

}

int invt[MAXN];

void poly_inv(int deg,int a[],int b[])

{

	if(deg == 1)

	{

		b[0] = power(a[0],P - 2);

		return;

	}

	poly_inv((deg + 1) >> 1,a,b);

	int l = init(deg * 2);

	for(int i = 0;i < deg;++i)invt[i] = a[i];

	for(int i = deg;i < l;++i)invt[i] = 0;

	NTT(invt,l,1);NTT(b,l,1);

	for(int i = 0;i < l;++i)b[i] = (2ll * b[i] - 1ll * invt[i] * b[i] % P * b[i] % P + P) % P;

	NTT(b,l,-1);

	for(int i = deg;i < l;++i)b[i] = 0;

	for(int i = 0;i < l;++i)invt[i] = 0;

	return;

}

int lnt[MAXN];

void poly_ln(int deg,int a[],int b[])

{

	poly_inv(deg,a,lnt);

	for(int i = 0;i < deg;++i)b[i] = a[i];

	for(int i = 0;i < deg;++i)b[i] = 1ll * (i + 1) * b[i + 1] % P;

	int l = init(deg * 2);

	NTT(lnt,l,1);NTT(b,l,1);

	for(int i = 0;i < l;++i)b[i] = 1ll * b[i] * lnt[i] % P;

	NTT(b,l,-1);

	for(int i = deg - 1;i >= 1;--i)b[i] = 1ll * inver(i) * b[i - 1] % P;b[0] = 0;

	for(int i = deg;i < l;++i)b[i] = 0;

	for(int i = 0;i < l;++i)lnt[i] = 0;

	return;

}

int expt[MAXN];

void poly_exp(int deg,int a[],int b[])

{

	if(deg == 1)

	{

		b[0] = 1;

		return;

	}

	poly_exp((deg + 1) >> 1,a,b);

	poly_ln(deg,b,expt);

	for(int i = 0;i < deg;++i)expt[i] = (a[i] - expt[i] + P) % P;

	expt[0] = (expt[0] + 1) % P;

	int l = init(deg * 2);

	NTT(expt,l,1);NTT(b,l,1);

	for(int i = 0;i < l;++i)b[i] = 1ll * b[i] * expt[i] % P;

	NTT(b,l,-1);

	for(int i = deg;i < l;++i)b[i] = 0;

	for(int i = 0;i < l;++i)expt[i] = 0;

	return;

}

int s[19][MAXN];

void solve(int d,int l,int r)

{

	if(l == r)

	{

		s[d][0] = 1;s[d][1] = (P - a[l]) % P;

		return;

	}

	int mid = ((l + r) >> 1);

	solve(d + 1,l,mid);

	for(int i = 0;i <= r - l + 1;++i)s[d][i] = s[d + 1][i];

	for(int i = 0;i <= r - l + 1;++i)s[d + 1][i] = 0;

	solve(d + 1,mid + 1,r);

	int len = init(r - l + 1);

	NTT(s[d],len,1);NTT(s[d + 1],len,1);

	for(int i = 0;i < len;++i)s[d][i] = 1ll * s[d][i] * s[d + 1][i] % P;

	NTT(s[d],len,-1);

	for(int i = 0;i < len;++i)s[d + 1][i] = 0;

	return;

}

int S[MAXN];

int fac[MAXN],inv[MAXN];

int A[MAXN],B[MAXN];

int C[MAXN],D[MAXN],E[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	int mul = 1;

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= n;++i)mul = 1ll * mul * a[i] % P;

	solve(0,1,n);

	poly_ln(n + 1,s[0],S);

	for(int i = 0;i <= n;++i)S[i] = 1ll * (i + 1) * S[i + 1] % P;

	for(int i = n;i >= 1;--i)S[i] = (P - S[i - 1]) % P;S[0] = n;

	fac[0] = 1;for(int i = 1;i <= n;++i)fac[i] = 1ll * fac[i - 1] * i % P;

	inv[n] = inver(fac[n]);for(int i = n - 1;i >= 0;--i)inv[i] = 1ll * inv[i + 1] * (i + 1) % P;

	for(int i = 0;i <= n;++i)A[i] = 1ll * power(i + 1,2 * m) * inv[i] % P;

	for(int i = 0;i <= n;++i)B[i] = 1ll * power(i + 1,m) * inv[i] % P;

	poly_inv(n + 1,B,C);

	int l = init(n * 2);

	NTT(C,l,1);NTT(A,l,1);

	for(int i = 0;i < l;++i)C[i] = 1ll * C[i] * A[i] % P;

	NTT(C,l,-1);

	for(int i = n + 1;i < l;++i)C[i] = 0;

	poly_ln(n + 1,B,D);

	for(int i = 0;i <= n;++i)C[i] = 1ll * C[i] * S[i] % P;

	for(int i = 0;i <= n;++i)D[i] = 1ll * D[i] * S[i] % P;

	poly_exp(n + 1,D,E);

	l = init(n * 2);

	NTT(C,l,1);NTT(E,l,1);

	for(int i = 0;i < l;++i)E[i] = 1ll * C[i] * E[i] % P;

	NTT(E,l,-1);

	cout << 1ll * E[n - 2] * fac[n - 2] % P * mul % P << endl;

	return 0;

}