专栏文章

题解 P5900 【无标号无根树计数】

WWeng_Weijie
P5900题解参与者 21已保存评论 23

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
23 条
当前快照
1 份
快照标识符
@mkhgvj1t
此快照首次捕获于
2026/01/17 06:45
2 个月前
此快照最后确认于
2026/01/17 06:45
2 个月前
查看原文

前言

虽然 Θ(nlog⁡2n)\Theta(n\log^2n) 也能过，但是没什么意义，只是跑的就是比 Θ(nlog⁡n)\Theta(n\log n) 快。
在我的博客里看可能公式会更好看。

Euler 变换简介

为了方便，这里介绍一下幂级数的 Euler\text{Euler} 变换。
Euler\text{Euler} 变换的其中一个定义式如下：
E(F(x))=∏i1(1−xi)fi\mathcal E(F(x))=\prod_i{\dfrac{1}{(1-x^i)^{f_i}}}
这个变换类似于 EGF\text{EGF} 中的 exp⁡\exp。
exp⁡F(x)=∑iFi(x)i!\exp F(x)=\sum_i\dfrac{F^i(x)}{i!}
EGF\text{EGF} 的 exp⁡\exp 具有的组合意义是：将 1∼n1\sim n 分成若干非空组，大小为 ii 的组内部具有 fif_i 中方案，问最后的总方案数。
而 Euler\text{Euler} 变换就是去除了这个标号的方案数，去掉标号会导致「如果两个组大小和内部方案均相同，则它们不可区分」。
因此 Euler\text{Euler} 的第一个定义式就易懂了。（即大小为 ii 的每种内部方案都可以选若干个，每种内部方案的生成函数都是 (1−xi)−1(1-x^i)^{-1}。）
现在有两种方法可以得到 Euler\text{Euler} 变换的第二个定义式。

方法一：使用指数、对数方法

=exp⁡(∑i−filn⁡(1−xi))=\exp\left(\sum_i-f_i\ln(1-x^i)\right) =exp⁡(∑ifi∑jxijj)=\exp\left(\sum_if_i\sum_{j}\dfrac{x^{ij}}j\right) =exp⁡(∑j1j∑ifixij)=\exp\left(\sum_j\dfrac 1j\sum_if_ix^{ij}\right) =exp⁡(∑jF(xj)j)=\exp\left(\sum_j\dfrac{F(x^j)}j\right)
因此我们得到了 Euler\text{Euler} 变换的第二个定义式。

方法二：使用 Burnside\text{Burnside} 引理 / Poˊlya\text{Pólya} 定理

首先枚举分成几个组，设有 nn 个。
这样的话，容易发现定理中的置换群即为 nn 元对称群 SnS_n。
定理内容即：对所有的 nn 元置换，求在该置换作用下不动点个数的平均值。
这时候考虑 kk 个位置构成 kk 阶循环的指数生成函数：
此时这 kk 个位置必须选择同样的方案，因此可以看做一个某个方案大小扩大了 kk 倍。同时 kk 个位置构成循环方案数即圆排列为 (k−1)!(k-1)!。
因此这个 EGF\text{EGF} 为
Ck(x)=1k!(k−1)!⋅F(xk)=F(xk)kC_k(x)=\dfrac{1}{k!}(k-1)!\cdot F(x^k)=\dfrac{F(x^k)}{k}
根据 exp⁡\exp 的组合意义，可以想到将所有 Ck(x)C_k(x) 相加，再做 exp⁡\exp 得到所有置换的贡献。
事实上这是正确的，原因是定理中的除以置换群大小（即 n!n!）与 EGF\text{EGF} 得到方案数时乘的 n!n! 抵消了。（难理解的话可以多设一个变元表示置换的大小以更好地理解）
同样得到了那个定义式：
E(F(x))=exp⁡(∑kF(xk)k)\mathcal E(F(x))=\exp\left(\sum_k\dfrac{F(x^k)}k\right)

回到原问题

解决无标号有根树计数问题

首先解决无标号有根树的问题。
容易发现，给定根以后，所有的子树可以理解成构成大小为 n−1n-1 的若干个组。
因此我们需要解的方程即：
F(x)=x⋅E(F(x))F(x)=x\cdot\mathcal E(F(x))

方法一：先求导再使用分治 FFT\text{FFT} 解决

将上式两边求导再同时乘上 xx（即使用 ϑ\vartheta 算子，xnx^n 项的系数乘以 nn）。
这里略去了一些中间步骤。
ϑF(x)=F(x)+F(x)(∑k≥1F′(xk)xk)\vartheta F(x)=F(x)+F(x)\left(\sum_{k\geq 1}F'(x^k)x^k\right)
设 G(x)=∑kF′(xk)xkG(x)=\sum\limits_kF'(x^k)x^k。
可以观察到 gn=∑d∣nfd⋅dg_n=\sum\limits_{d|n}f_d\cdot d。
因此 fn=1n−1(∑kfkgn−k)f_n=\dfrac{1}{n-1}\left(\displaystyle\sum_{k}f_kg_{n-k}\right)，f1=1f_1=1。
此时便可以使用分治 FFT\text{FFT} 解决这个问题。

方法二：Newton\text{Newton} 迭代法

我们需要解的方程是：
G(F(x))=F(x)−x⋅E(F(x))G(F(x))=F(x)-x\cdot\mathcal E(F(x))
假设当前已经求出了 F(x) mod xnF(x)\bmod{x^n}，需要求 F(x) mod x2nF(x)\bmod{x^{2n}}。
容易发现的是对 k≥2k\geq 2，我们已经知道了 F(xk)mod  x2nF(x^k)\mod {x^{2n}} 的值。
这时我们可以用一个常数来代替它。（强调一下这不代表它原来是一个常数，也就是说 F(x2)F(x^2) 对 F(x)F(x) 求导并不是 00）。
设
P(x)=(xexp⁡(∑k≥2F(xk)k)) mod x2nP(x)=\left(x\exp\left(\sum_{k\geq 2}\dfrac{F(x^k)}k\right)\right)\bmod{x^{2n}}
由于 P(x)P(x) 是我们规定的一个常数，则
F(x)≡P(x)exp⁡F(x)(modx2n)F(x)\equiv P(x)\exp F(x)\pmod{x^{2n}}
这个形式就易于 Newton\text{Newton} 迭代了，具体过程不详细介绍了。
事实上这个方法需要做 exp⁡\exp，导致常数比较大，实现不优秀很有可能比前一个方法慢。

解决无标号无根树计数问题

这个问题思路大概是：用有根树的方案减去根不是重心的方案。
当 nn 是奇数时：
如果根不是重心，必然存在恰好一个子树，它的大小超过 ⌊n2⌋\left\lfloor\dfrac n2\right\rfloor（设它的大小为 kk），那么这个子树和这棵子树以外的其他点的方案数恰好为 fk⋅fn−kf_k\cdot f_{n-k}（可以看成两棵有根树）。
因此答案为 fn−∑k=⌊n2⌋+1n−1fk⋅fn−kf_n-\sum_{k=\lfloor\frac n2\rfloor+1}^{n-1}f_k\cdot f_{n-k}
当 nn 是偶数时：
出现的问题是，有可能存在两个重心，且其中一个是根（即存在一棵子树大小恰为 n2\dfrac n2）。
那么如果这个子树和剥离该子树后的树完全相同，这样的方案在 fnf_n 只会计算一次，即不需要减去。
如果这个子树和另一棵树不相同，会被统计两次，需要减掉一次。
因此偶数时额外减掉的方案数为
(fn22)\binom{f_{\frac n2}}2
至此，这个问题在 O(nlog⁡n)O(n\log n) 或 O(nlog⁡2n)O(n\log^2n) 的时间复杂度内解决。

参考代码：

CPP
#include <bits/stdc++.h>

typedef long long LL;
typedef unsigned long long ULL;
const int mod = 998244353, N = 262144;

int wn[N], lim, s, rev[N], w[N];
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;
}
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) {
	static ULL tmp[N];
	for (int i = 0; i < lim; ++i) tmp[rev[i]] = A[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 ULL x = tmp[k + j + i] * w[k] % mod;
				tmp[k + j + i] = tmp[k + j] + mod - x, tmp[k + j] += x;;
			}
	}
	for (int i = 0; i < lim; ++i) A[i] = tmp[i] % mod;
	if (!typ) {
		const int il = pow(lim, mod - 2); std::reverse(A + 1, A + lim);
		for (int i = 0; i < lim; ++i) A[i] = (LL) A[i] * il % mod;
	}
}

int inv[N];
int f[N], g[N], n;
int a[N], b[N];

void init(int n) {
	inv[0] = 1, inv[1] = 1;
	for (int i = 2; i < n; ++i)
		inv[i] = (LL) (mod - mod / i) * inv[mod % i] % mod;
}

void solve(int l, int r) {
	if (r - l <= 32) {
		for (int i = l; i < r; ++i) {
			for (int j = l; j < i; ++j) {
				f[i] = (f[i] + (LL) f[j] * g[i - j]) % mod;
				if (l > 1) f[i] = (f[i] + (LL) g[j] * f[i - j]) % mod;
			}
			f[i] = (LL) f[i] * inv[i - 1] % mod;
			int v = (LL) f[i] * i % mod;
			for (int p = i; p <= n; p += i) reduce(g[p] += v - mod);
		}
		return;
	}
	int mid = l + r + 1 >> 1;
	solve(l, mid), fftinit(r - l);
	auto update = [&] (int *f, int la, int *g, int lb) {
		std::memcpy(a, f, la << 2), std::memset(a + la, 0, lim - la << 2);
		std::memcpy(b, g, lb << 2), std::memset(b + lb, 0, lim - lb << 2);
		fft(a, 1), fft(b, 1);
		for (int i = 0; i < lim; ++i) a[i] = (LL) a[i] * b[i] % mod;
		fft(a, 0);
		for (int i = mid; i < r; ++i) reduce(::f[i] += a[i - l] - mod);
	};
	if (l > 1) update(f + l, mid - l, g, r - l);
	update(g + l, mid - l, f, l == 1 ? mid : r - l);
	solve(mid, r);
}

int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	std::cin >> n, f[1] = 1, init(n), solve(1, n + 1);
	int ans = f[n];
	for (int i = n / 2 + 1; i < n; ++i)
		ans = (ans + (LL) (mod - f[i]) * f[n - i]) % mod;
	if (n % 2 == 0) ans = (ans + mod - (LL) f[n / 2] * (f[n / 2] - 1) / 2 % mod) % mod;
	std::cout << ans << '\n';
	return 0;
}

评论

共 23 条评论，欢迎与作者交流。

正在加载评论...