一道自己出的小菜题。

题目链接

题意：有多少张无自环、无重边的 $n$ 个点带标号无向连通图，它的生成树个数 $ \leqslant k $。（$n \leqslant 10^6$，$k \leqslant 22$）

一张图的生成树个数为每个点双生成树个数之积。

一个点数$> 2$的点双，生成树个数至少为$3$。那么点数$> 2$的点双不超过$2$个。

对于一个点双，如果$m = n$，那么只能是一个环，生成树个数为$n$，方案数为$\frac{(n - 1)!}{2}$。

对于一个点双，如果$m = n + 1$，一定是两个点之间三条路径，观察一下发现生成树个数最少的情况是这三条路径中的两条长分别为$1$和$2$，此时生成树个数为$3n - 4$。（证明较为简单，就不讲了）

那么如果一个点双需要满足$m \geqslant n + 1$，因为$k \leqslant 22$，所以$n$必须$\leqslant 8$。那么我们可以在$2^{\frac{1}{2}n(n-1)}n^3$的时间内用搜索$+$矩阵树对于$\leqslant 8$的$n$打出一张表，内容为$n$个点生成树个数为$i(i \leqslant 22)$的点双一共有多少种。

最后枚举两个点双的大小、生成树个数，随便算一下答案就好了。

（打表程序本机需要跑$8\text{min}$。)

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6, mod = 998244353, inv2 = (mod + 1) >> 1;
int f[100][100], n, s, ans, tot;
int fac[maxn + 10], inv[maxn + 10], ifac[maxn + 10];

inline int add(int x, int y) {
	x += y; return x < mod ? x : x - mod;
}
inline int dec(int x, int y) {
	x -= y; return x < 0 ? x + mod : x;
}
inline int mul(int x, int y) {
	return 1ll * x * y % mod;
}
inline int fpow(int x, int y) {
	if (y < 0) return fpow(fpow(x, -y), mod - 2);
	int ans = 1;
	while (y) {
		if (y & 1) ans = mul(ans, x);
		y >>= 1; x = mul(x, x);
	}
	return ans;
}

void pre() {
	f[3][3]=1;
	f[4][4]=3;
	f[4][8]=6;
	f[4][16]=1;
	f[5][5]=12;
	f[5][11]=60;
	f[5][12]=10;
	f[5][20]=10;
	f[5][21]=60;
	f[6][6]=60;
	f[6][14]=360;
	f[6][15]=180;
	f[6][16]=180;
	f[7][7]=360;
	f[7][17]=2520;
	f[7][19]=2520;
	f[7][20]=1260;
	f[7][21]=1260;
	f[8][8]=2520;
	f[8][20]=20160;
	for (int i = 9; i <= 22; ++i)
		f[i][i] = mul(f[i - 1][i - 1], i - 1);
	fac[0] = ifac[0] = 1;
	for (int i = 1; i <= maxn; ++i) {
		inv[i] = i == 1 ? 1 : dec(0, mul(mod / i, inv[mod % i]));
		fac[i] = mul(fac[i - 1], i);
		ifac[i] = mul(ifac[i - 1], inv[i]);
	}
}
int comb(int x, int y) {
	return mul(fac[x], mul(ifac[y], ifac[x - y]));
}
int main() {
	pre();
	scanf("%d%d", &n, &s);
	ans = fpow(n, n - 2);
	for (int i = 3; i <= 22; ++i)
		for (int j = 3; j <= 22; ++j)
			if (i <= n && j <= s) {
				ans = add(ans, mul(comb(n, i), mul(f[i][j], mul(i, fpow(n, n - i - 1)))));
			}
	for (int i = 3; i <= 22; ++i)
		for (int j = 3; j <= 22; ++j)
			for (int k = 3; k <= 22; ++k)
				for (int l = 3; l <= 22; ++l) {
					if (i + k <= n && j * l <= s) {
						int w = mul(comb(n, i), comb(n - i, k));
						w = mul(w, mul(i, k));
						w = mul(w, fpow(n, n - i - k));
						w = mul(w, mul(f[i][j], f[k][l]));
						tot = add(tot, w);
					}
					if (i + k - 1 <= n && j * l <= s) {
						int w = mul(n, mul(comb(n - 1, i - 1), comb(n - i, k - 1)));
						w = mul(w, i + k - 1);
						w = mul(w, fpow(n, n - i - k));
						w = mul(w, mul(f[i][j], f[k][l]));
						tot = add(tot, w);
					}
				}
	ans = add(ans, mul(tot, inv2));
	printf("%d", ans);
}