题意

定义一个无向图的权值为所有结点度数的 $k$ 次方之和（规定 $0^0=1$ ）。

求所有 $n$ 个点的简单无向图的权值之和。

答案对 998244353 取模。

$n\leq10^9,0\leq k\leq5\times10^5$ 。

题解

可以对于每个点的贡献然后乘 $n$ 。考虑每个点贡献的组合意义，相当于是 $k$ 个有标号点放进 $d$ 个有标号桶里，并且可以有空。那么就有：

$$n\sum_{d=0}^{n-1}d^k=n\sum_{d=0}^{n-1}\sum_{i=0}^k\begin{Bmatrix} k \\i \end{Bmatrix}\binom{d}{i}i!=n\sum_{i=0}^k\begin{Bmatrix} k \\i \end{Bmatrix}i!\sum_{d=0}^{n-1}\binom{d}{i} $$

其中 $i$ 枚举的是多少个非空桶。

考虑组合数和式，其意义相当于 $\forall i\in[1,k]$ ，要求所有简单无向图中 $1$ 号点连的边中选出 $i$ 条的方案数之和。

那么先选出 $i$ 条边，再看别的边选不选（那这些任选），也就是 $\binom{n-1}{i}2^{\frac{n(n-1)}{2}-i}$ 。

处理斯特林数 NTT 即可。

代码

const int N = 5e5 + 10, mod = 998244353, G = 3, invG = 332748118;
const int pN = N << 3;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	#define clr(f, x) memset(f, 0, sizeof(int) * (x))
	#define cpy(f, g, x) memcpy(f, g, sizeof(int) * (x))
	int add (int x, int y) { return x + y > mod? x + y - mod: x + y; }
	int dec (int x, int y) { return x - y < 0? x - y + mod: x - y; }
	int mul (int x, int y) { return 1ll * x * y % mod; }
	int qpow (int a, ll b) {
		int ans = 1;
		for (; b; b >>= 1, a = mul(a, a))
			if (b & 1) ans = mul(ans, a);
		return ans;
	}
	int n, k;
	struct poly {
		int tr[pN];

		void init(int n, int siz) {
			for (int i = 0; i < n; ++i)
				tr[i] = (tr[i >> 1] >> 1) | ((i & 1) << (siz - 1));
		}

		void NTT(int *f, int n, int op = 1) {
			for (int i = 0; i < n; i++)
				if (i < tr[i]) swap(f[i], f[tr[i]]);
			for (int p = 1; p < n; p <<= 1) {
				int omega = qpow(op? G: invG, (mod - 1) / (p << 1));
				for (int j = 0; j <	n; j += p << 1) 
					for (int w = 1, k = 0; k < p; k++, w = mul(w, omega)) {
						int x = f[j | k], y = mul(w, f[j | p | k]);
						f[j | k] = add(x, y), f[j | p | k] = dec(x, y);
					}
			}
			if (!op) {
				int invn = qpow(n, mod - 2);
				for (int i = 0; i < n; i++) f[i] = mul(f[i], invn);
			}
		}
		void times (int *f, int *g, int n, int m, int T) {
			int lim = 1, lsiz = 0; for (; lim < n + m; lim <<= 1, lsiz++);
			init(lim, lsiz);
			static int tmp[pN]; clr(f + n, lim - n), cpy (tmp, g, m), clr(tmp + m, lim - m);
			NTT(f, lim), NTT(tmp, lim);
			for (int i = 0; i < lim; i++) f[i] = mul(f[i], tmp[i]);
			NTT(f, lim, 0);
			clr (f + T, lim - 1), clr (tmp, lim);
		}
	} p;
	int S[N], f[pN], g[pN];
	int fac[N], inv[N], invs[N];
	void getS() {
		fac[0] = 1;	for (int i = 1; i < N; i++) fac[i] = mul(fac[i - 1], i);
		inv[0] = inv[1] = 1; for (int i = 2; i < N; i++) inv[i] = mul(inv[mod % i], mod - mod / i);
		invs[0] = 1; for (int i = 1; i < N; i++) invs[i] = mul(invs[i - 1], inv[i]);
		for (int i = 0; i <= k; i++) {
			f[i] = mul((i & 1)? mod - 1: 1, invs[i]);
			g[i] = mul(qpow(i, k), invs[i]);
		}
		p.times(f, g, k + 1, k + 1, k + 1);
		for (int i = 0; i <= k; i++) S[i] = f[i];
	}
	int main () {
		n = Read(), k = Read();
		getS();
		int ans = 0, CC = 1, inv2 = qpow(2, mod - 2), sum2 = qpow(2, 1ll * n * (n - 1) / 2);
		for (int i = 0; i <= k; i++) {
			ans = add(ans, mul(S[i], mul(mul(CC, mul(sum2, qpow(inv2, i))), fac[i])));
			CC = mul(CC, mul(n - i - 1, inv[i + 1]));
		}
		printf ("%d\n", mul(ans, n));
		return 0;
	}
}

int main () {
	freopen("graph.in", "r", stdin);
	freopen("graph.out", "w", stdout);
	Main::main();
	return 0;
}