洛谷P5219 无聊的水题 I

传送门

题目背景

出题人过菜，只会出这种题，稍微有点卡常。

题目描述

DLS 喜欢上树。
但是他并不想把一道数据结构题出到树上，他喜欢计 Tree。

这一天，他想自己造一棵树，他手头有 NN 个树的节点，标号为 1 \sim N1∼N，他会在它们之间连边，我们定义两颗树不同，当且仅当一对节点在一棵树中有连边，另一棵树中没有连边。
但他不喜欢一棵太多分叉的树，于是他想让这棵树的节点中最大的度数为 MM。

DLS 由于不太擅长理科，所以希望你帮他计算有多少棵这样的树。 答案对 998244353998244353 取模。

输入格式

一行两个整数 N, MN,M。

输出格式

一行一个整数表示答案。

输入输出样例

输入 #1复制
3 2
输出 #1复制
3
输入 #2复制
7 4
输出 #2复制
2520

说明/提示

数据百分比 限制
10%10% N,M \le 8N,M≤8
30%30% N,M \le 100N,M≤100
50%50% N,M \le 500N,M≤500
70%70% N,M \le 2000N,M≤2000
100%100% 2 \le N,M \le 5 \times 10^42≤N,M≤5×10
4

上代码：

#include 
#include 
#include 

const int mod = 998244353;
const int N = 131072;
using LL = long long;
void reduce(int &x) {
	x += x >> 31 & mod;
}
int pow(int x, int y, int ans = 1) {
	for (; y; y >>= 1, x = (LL) x * x % mod)
		if (y & 1) ans = (LL) ans * x % mod;
	return ans;
}
int lim, s, rev[N], wn[N], w[N];
void fftinit(int len) {
	wn[0] = lim = 1, s = -1; while (lim < len) lim <<= 1, ++s;
	for (int i = 0; i < lim; ++i) rev[i] = rev[i >> 1] >> 1 | (i & 1) << s;
	const int g = pow(3, (mod - 1) / lim);
	for (int i = 1; i < lim; ++i) wn[i] = (LL) wn[i - 1] * g % mod;
}
void fft(int *A, int typ) {
	for (int i = 0; i < lim; ++i) if (i < rev[i]) std::swap(A[i], A[rev[i]]);
	for (int i = 1; i < lim; i <<= 1) {
		for (int j = 0, t = lim / i / 2; j < i; ++j) w[j] = wn[j * t];
		for (int j = 0; j < lim; j += i << 1)
			for (int k = 0; k < i; ++k) {
				const int x = A[k + j], y = (LL) A[k + j + i] * w[k] % mod;
				reduce(A[k + j] += y - mod), reduce(A[k + j + i] = x - y);
			}
	}
	if (!typ) {
		const int il = pow(lim, mod - 2);
		for (int i = 0; i < lim; ++i) A[i] = (LL) A[i] * il % mod;
		std::reverse(A + 1, A + lim);
	}
}
void inv(int *A, int *B, int n) {
	static int C[N], D[N];
	if (n == 1) { B[0] = pow(A[0], mod - 2); return; }
	int n_ = n + 1 >> 1; inv(A, B, n_), fftinit(n + n_ + 1);
	std::memcpy(C, A, n << 2), std::memset(C + n, 0, lim - n << 2);
	std::memcpy(D, B, n_ << 2), std::memset(D + n_, 0, lim - n_ << 2);
	fft(C, 1), fft(D, 1);
	for (int i = 0; i < lim; ++i)
		C[i] = (mod + 2 - (LL) C[i] * D[i] % mod) * D[i] % mod;
	fft(C, 0);
	std::memcpy(B + n_, C + n_, n - n_ << 2);
}
void differential(int *A, int *B, int n) {
	for (int i = 0; i < n - 1; ++i)
		B[i] = (LL) A[i + 1] * (i + 1) % mod;
	B[n - 1] = 0;
}
void integrate(int *A, int *B, int n) {
	for (int i = n - 1; ~i; --i)
		B[i + 1] = (LL) A[i] * pow(i + 1, mod - 2) % mod;
	B[0] = 0;
}
void ln(int *A, int *B, int n) {
	static int C[N], D[N];
	inv(A, C, n), differential(A, D, n);
	fftinit(n + n - 1);
	std::memset(C + n, 0, lim - n << 2), std::memset(D + n, 0, lim - n << 2);
	fft(C, 1), fft(D, 1);
	for (int i = 0; i < lim; ++i)
		C[i] = (LL) C[i] * D[i] % mod;
	fft(C, 0);
	integrate(C, B, n);
}
void exp(int *A, int *B, int n) {
	static int C[N], D[N];
	if (n == 1) { B[0] = 1; return; }
	int n_ = n + 1 >> 1; exp(A, B, n_);
	ln(B, C, n), fftinit(n + 1);
	for (int i = 0; i < n; ++i) reduce(C[i] = A[i] - C[i]);
	std::memset(C + n, 0, lim - n << 2);
	std::memcpy(D, B, n_ << 2), std::memset(D + n_, 0, lim - n_ << 2);
	fft(C, 1), fft(D, 1);
	for (int i = 0; i < lim; ++i)
		C[i] = (LL) C[i] * D[i] % mod;
	fft(C, 0);
	std::memcpy(B + n_, C + n_, n - n_ << 2);
}
int n, m, f[N], g[N], factor[N], ifactor[N];

int get_ans(int m) {
	std::memset(f, 0, sizeof f), std::memset(g, 0, sizeof g);
	for (int i = 0; i < m; ++i) f[i] = ifactor[i];
	ln(f, g, n - 1);
	for (int i = 0; i < n - 1; ++i)
		f[i] = 0, g[i] = (LL) g[i] * n % mod;
	exp(g, f, n - 1);
	return (LL) f[n - 2] * factor[n - 2] % mod;
}
int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	std::cin >> n >> m;
	factor[0] = 1;
	for (int i = 1; i < n - 1; ++i)
		factor[i] = (LL) factor[i - 1] * i % mod;
	ifactor[n - 2] = pow(factor[n - 2], mod - 2);
	for (int i = n - 3; ~i; --i)
		ifactor[i] = (LL) ifactor[i + 1] * (i + 1) % mod;
	int ans = get_ans(m) - get_ans(m - 1); reduce(ans);
	std::cout << ans << '\n';
	return 0;
}

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