Description：

定义一个无向图的权值为所有结点度数的 $k$ 次方之和。求所有 $n$ 个点的简单无向图(共有 $2^{C^n_2}$ 个)的权值之和。

答案对 $998244353$ 取模。

$1\leqslant n\leqslant 10^9,1\leqslant k\leqslant5\times 10^5$

Solution：

$$ \begin{align} ans&=\sum_G\sum_{i=1}^ndeg_G[i]^k\\ &=n\times\sum_Gdeg[1]^k\\ &=n\sum_{d=0}^{n-1}d^k\times C^{n-1}_d2^{C^{n-1}_2} \end{align} $$

$C^{n-1}_d$ 这一行组合数可以逐个递推出来，所以我们其实就是要求： $$ \sum_{d=0}^nd^kC^n_d $$

然后根据公式： $$ x^k=\sum_{i=0}^k\left\{\begin{aligned}k\\i\end{aligned}\right\}x^{\underline i}=\sum_{i=0}^k\left\{\begin{aligned}k\\i\end{aligned}\right\}C^x_ii! $$ 把原式展开可得： $$ \sum_{d=0}^n\sum_{i=0}^k\left\{\begin{aligned}k\\i\end{aligned}\right\}C^d_ii!C^n_d $$ 交换求和号，会发现最后是一个： $$ \sum_{d=0}^nC^d_iC^n_d $$ 的形式，然后会发现： $$ \sum_{d=0}^nC^d_iC^n_d=C^n_i\sum_{d=0}^nC^{n-i}_{d-i}=C^n_i\sum_{d=0}^{n-i}C^{n-i}_d=C^n_i2^{n-i} $$ 所以只要能快速求出第二类斯特林数，就可以 $O(k\log n)$ 求解答案了，预处理第二类斯特林数可以用公式： $$ \left\{\begin{aligned}n\ \\m\end{aligned}\right\}=\frac{1}{m!}\sum_{i=0}^mC_m^i(-1)^i(m-i)^n $$ 把组合数拆开后会发现是一个卷积的形式，于是用 $NTT$ 即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

ll n,k;

#define MAXN 2000010

ll s[MAXN];

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

int rev[MAXN];

#define P 998244353

ll a[MAXN],b[MAXN];

ll fac[MAXN],inv[MAXN];

ll power(ll a,ll b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % P;

		a = a * a % P;

		b = b >> 1;

	}

	return res;

}

ll C(ll n,ll m)

{

	return fac[n] * inv[m] % P * inv[n - m] % P;

}

void NTT(ll 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)

	{

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

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

		{

			ll w = 1;

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

			{

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

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

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

				w = w * wn % P;

			}

		}

	}

	if(type == -1)

	{

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

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

	}

	return;

}

void init()

{

	fac[0] = 1;

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

	inv[k] = power(fac[k],P - 2);

	for(int i = k - 1;i >= 0;--i)inv[i] = (i + 1) * inv[i + 1] % P;

	for(int i = 0;i <= k;++i)a[i] = power(P - 1,i) * inv[i] % P;

	for(int i = 0;i <= k;++i)b[i] = power(i,k) * inv[i] % P;

	int l = 0,len = 1;

	for(;len <= (k << 1);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] = g[i - 1] * g[1] % P;

	NTT(a,len,1);NTT(b,len,1);

	for(int i = 0;i < len;++i)s[i] = a[i] * b[i] % P;

	NTT(s,len,-1);NTT(a,len,-1);NTT(b,len,-1);

	return;

}

ll c[MAXN];

int main()

{

	freopen("graph.in","r",stdin);

	freopen("graph.out","w",stdout);

	scanf("%lld%lld",&n,&k);

	init();

	ll sum = 0;

	c[0] = 1;

	for(int i = 1;i <= min(n - 1,k);++i)c[i] = c[i - 1] * (n - i) % P * power(i,P - 2) % P;

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

	{

		sum = (sum + s[i] * fac[i] % P * c[i] % P * power(2,n - 1 - i) % P) % P;

	}

	sum = sum * power(2,(n - 1) * (n - 2) / 2) % P * n % P;

	cout << sum << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}