• 欢迎光临~

Luogu 7728. 旧神归来(Return of Them)

开发技术 开发技术 2022-08-03 次浏览

有一棵树,生长规则如下:

  • 初始有一棵包含 (n) 个结点的以 (1) 为根的有根树 (T_0)
  • 在第 (i) 天,树将从 (T_{i - 1}) 生长为 (T_i),生长规则为:令 (v)(T_{i - 1})深度最小的叶结点(若有多个则任意选择一个),以 (v) 这个点替换成 (T_{i - 1}) 本身。

需要计算:

  • 对于每个整数 (d in [1, m]),求出 (S_d) 表示最小的天数,满足 (T_{S_d}) 中深度最小的叶结点深度大于 (d)

答案对 (998244353) 取模。
(2 le n, m le {10}^5)


考虑操作只与叶子节点组成的深度可重集合有关,设 (S) 为所有叶子节点组成的深度可重集合,观察一次操作前后的变化:

  • 设替换的叶子节点的深度为 (d),那么少了一个 (d),多了一族 (S+d)

尝试用生成函数表达这一过程,设 (F)(S)(text{OGF})。一次操作即为:

[F(x)leftarrow (1+x^d)F(x)-x^d ]

设深度为 (i) 的点操作了 (a_i) 次,推导可得

[prod_{ige1} (1+x^i)^{a_i}(F(x)-1)=-1 ]

[prod_{ige1} (1+x^i)^{a_i}=frac{1}{1-F(x)} ]

两边同时取 (ln)

[sum_{ige1} a_iln (1+x^i)=ln frac{1}{1-F(x)} ]

[begin{aligned}ln(1-x^n)&=int frac{text{d}}{text{d}x}ln(1-x^n)=-intfrac{nx^{n-1}}{1-x^n}\ &=-int sum_{tge 0}nx^{(t+1)n-1}=-int sum_{tge1}nx^{tn-1}=-sum_{tge 1}frac{x^{tn}}{t}\ end{aligned} ]

根据这个公式,将 (-x^i) 代入,得

[sum_{ij=n} frac{(-1)^{j-1}a_i}{j}=[x^n]frac{1}{1-F(x)} ]

(O(nlog n)) 求出 (frac{1}{1-F(x)}),然后再 (O(nlog n)) 解出 (a_i) 即可。

#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef long long ll;
typedef vector<int> Poly;
const int N = 1 << 20, mod = 998244353, inv2 = mod + 1 >> 1;
int n, m, sum, r[N], ans[N], dep[N], Inv[N];
vector<int> G[100005]; Poly S;
inline int add(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }
inline int dec(int x, int y) { return x - y < 0 ? x - y + mod : x - y; }
inline int mul(int x, int y) { return (ll)x * y % mod; }
inline int qpow(int a, int b) {
	int ans = 1;
	for (; b; b >>= 1, a = mul(a, a)) if (b & 1) ans = mul(ans, a);
	return ans;
}
inline void NTT(Poly &A, int len, int type){
	for (int i = 0; i < len; ++ i) if(i < r[i]) swap(A[i], A[r[i]]);
	for (int mid = 1; mid < len; mid <<= 1) {
		int Wn = qpow(type == 1 ? (mod + 1) / 3 : 3, (mod - 1) / (mid << 1));
		for (int j = 0; j < len; j += (mid << 1))
			for (int k = 0, w = 1; k < mid; ++ k, w = mul(w, Wn)) {
				int x = A[j + k], y = mul(w, A[j + k + mid]);
				A[j + k] = add(x, y), A[j + k + mid] = dec(x, y);
			}
	}
	if (type > 0) return;
	for (int i = 0; i < len; ++ i) A[i] = mul(A[i], Inv[len]);
}
inline void init_rev(int len) {
	for (int i = 0; i < len; ++ i) r[i] = r[i >> 1] >> 1 | ((i & 1) * (len >> 1));
}
inline Poly operator + (const Poly&a, const Poly&b) {
	Poly c = a; c.resize(max(a.size(), b.size()));
	for (int i = 0; i < b.size(); ++ i) c[i] = add(c[i], b[i]);
	return c;
}
inline Poly operator - (const Poly&a, const Poly&b) {
	Poly c = a; c.resize(max(a.size(), b.size()));
	for (int i = 0; i < b.size(); ++ i) c[i] = dec(c[i], b[i]);
	return c;
}
inline Poly operator * (Poly a, Poly b) {
	int n = a.size(), m = b.size(), l = 1;
	while (l < n + m - 1) l <<= 1;
	init_rev(l);
	a.resize(l), NTT(a, l, 1);
	b.resize(l), NTT(b, l, 1);
	for (int i = 0; i < l; ++ i) a[i] = mul(a[i], b[i]);
	NTT(a, l, -1);
	a.resize(n + m - 1);
	return a;
}
inline Poly operator * (Poly a, int b) {
	for (int i = 0; i < a.size(); ++ i) a[i] = mul(a[i], b);
	return a;
}
inline Poly Deriv(Poly a) {
	for (int i = 0; i + 1 < a.size(); ++ i) a[i] = mul(a[i + 1], i + 1);
	return a.pop_back(), a;
}
inline Poly Integ(Poly a) {
	a.emplace_back(0);
	for (int i = a.size() - 1; i; -- i) a[i] = mul(a[i - 1], Inv[i]);
	return a[0] = 0, a;
}
inline Poly Polyinv(const Poly&a, int lim) {
	Poly c, b(1, qpow(a[0], mod - 2));
	for (int l = 4; (l >> 2) < lim; l <<= 1) {
		init_rev(l);
		c = a, c.resize(l >> 1);
		c.resize(l), NTT(c, l, 1);
		b.resize(l), NTT(b, l, 1);
		for (int i = 0; i < l; ++ i) b[i] = mul(b[i], dec(2, mul(b[i], c[i])));
		NTT(b, l, -1), b.resize(l >> 1);
	}
	return b.resize(lim), b;
}
inline Poly Polyinv(const Poly&a) { return Polyinv(a, a.size()); }
inline Poly Polyln(Poly a, int lim) {
	a = Integ(Deriv(a) * Polyinv(a, lim));
	return a.resize(lim), a;
}
inline Poly Polyln(const Poly&a) { return Polyln(a, a.size()); }
inline Poly Polyexp(const Poly&a, int lim) {
	Poly c, b(1, 1); int n = a.size();
	for (int i = 2; (i >> 1) < lim; i <<= 1) {
		c = Polyln(b, i);
		for (int j = 0; j < i; ++ j) c[j] = dec(j < n ? a[j] : 0, c[j]);
		c[0] = add(c[0], 1);
		b = b * c, b.resize(i);
	}
	return b.resize(lim), b;
}
inline Poly Polyexp(const Poly&a) { return Polyexp(a, a.size()); }
inline Poly Polysqrt(const Poly&a, int lim) {
	Poly c, d, b(1, 1);
	for (int l = 4; (l >> 2) < lim; l <<= 1) {
		init_rev(l);
		c = a, c.resize(l >> 1);
		d = Polyinv(b, l >> 1);
		c.resize(l), NTT(c, l, 1);
		d.resize(l), NTT(d, l, 1);
		for (int j = 0; j < l; ++ j) c[j] = mul(c[j], d[j]);
		NTT(c, l, -1), b.resize(l >> 1);
		for (int j = 0; j < (l >> 1); ++ j) b[j] = mul(add(b[j], c[j]), inv2);
	}
	return b.resize(lim), b;
}
inline Poly Polysqrt(const Poly&a) { return Polysqrt(a, a.size()); }
inline Poly Polypow(Poly a, int k, int lim) {
	a = Polyexp(Polyln(a) * k);
	return a.resize(lim), a;
}
inline Poly Polypow(const Poly&a, int k) { return Polypow(a, k, a.size()); }
inline void precalc() {
	Inv[0] = Inv[1] = 1;
	for (int i = 2; i < N; ++ i) Inv[i] = mul(mod - mod / i, Inv[mod % i]);
}
inline void dfs(int x, int fa) {
	int fl = 0;
	for (auto y : G[x]) if (y ^ fa)
		dep[y] = dep[x] + 1, dfs(y, x), fl = 1;
	if (!fl) S[dep[x]] = dec(S[dep[x]], 1);
}
int main() {
	precalc();
	scanf("%d%d", &n, &m);
	for (int i = 1, x, y; i < n; ++ i) {
		scanf("%d%d", &x, &y);
		G[x].eb(y), G[y].eb(x);
	}
	S.resize(max(n, m) + 5);
	S[0] = 1;
	dfs(1, 0);
	Poly T = Polyln(S);
	for (int i = 1; i <= m; ++ i) {
		ans[i] = dec(ans[i], T[i]);
		for (int j = 2; j <= m / i; ++ j)
			ans[i * j] = j & 1 ? dec(ans[i * j], mul(ans[i], Inv[j])) : add(ans[i * j], mul(ans[i], Inv[j]));
	}
	for (int i = 1; i <= m; ++ i) printf("%dn", sum = add(sum, ans[i]));
}
程序员灯塔
转载请注明原文链接:Luogu 7728. 旧神归来(Return of Them)
喜欢 (0)