[codeforces438E]The Child and Binary Tree

试题描述

Our child likes computer science very much, especially he likes binary trees.

Consider the sequence of n distinct positive integers: \(c_1, c_2, \cdots , c_n\). The child calls a vertex-weighted rooted binary tree good if and only if for every vertex v, the weight of v is in the set \(\{c_1, c_2, \cdots , c_n\}\). Also our child thinks that the weight of a vertex-weighted tree is the sum of all vertices' weights.

Given an integer \(m\), can you for all \(s (1 \le s \le m)\) calculate the number of good vertex-weighted rooted binary trees with weight \(s\)? Please, check the samples for better understanding what trees are considered different.

We only want to know the answer modulo \(998244353\) (\(7 \times 17 \times 223 + 1\), a prime number).

给出 \(n\) 种点的点权，定义一棵二叉树的权值等于它所有点的点权和。求对于 \([1, m]\) 中的 \(s\)，权值为 \(s\) 的不同的二叉树有多少种。两棵二叉树不同当且仅当它们的左子树、右子树或根节点点权不同。一棵二叉树中可以出现多个点权相同的点。

输入

The first line contains two integers \(n, m (1 \le n \le 10^5; 1 \le m \le 10^5)\). The second line contains n space-separated pairwise distinct integers \(c_1, c_2, ..., c_n\). \((1 \le c_i \le 10^5)\).

输出

Print \(m\) lines, each line containing a single integer. The \(i\)-th line must contain the number of good vertex-weighted rooted binary trees whose weight exactly equal to \(i\). Print the answers modulo \(998244353\) (\(7 \times 17 \times 2^{23} + 1\), a prime number).

输入示例

3 10

9 4 3

输出示例

数据规模及约定

见“输入”

题解

首先看看暴力 dp 怎么解决这个问题。设 \(f_k\) 表示权值为 \(k\) 的二叉树的数目，那么有转移方程（注意 dp 边界）：

\[f_k = \sum_{i=1}^n { \sum_{j=0}^{k-c_i} f_{k-j-c_i} \cdot f_j } \\\\
f_0 = 1
\]

然后搞生成函数，令 \(C(x) = \sum_{i=1}^n { x^{c_i} }\)，\(F(x) = \sum_{i=0}^{+ \infty} { f_i \cdot x^i }\)。

然后我们发现里面的 sigma 是一个卷积，然后把式子缩一点：

\[[x^k]F(x) = \sum_{i=1}^n { 1 \cdot [x^{k-c_i}]F^2(x) } \\\\
[x^0]F(x) = 1
\]

然后前面那个 \(1\)，由于只在幂是 \(c_i\) 的时候出现，可以想象 \(C(x)\) 又在和 \(F^2(x)\) 做卷积，即

\[[x^k]F(x) = \sum_{i=1}^n { [x^{c_i}]C(x) \cdot [x^{k-c_i}]F^2(x) } \\\\
[x^0]F(x) = 1
\]

然后我们发现可以化成初中学过的二元一次方程的形式：

\[F(x) = C(x)F^2(x) + 1
\]

用 \(x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}\) 求根公式解一下上面这个关于 \(F(x)\) 的方程，得到

\[F(x) = \frac{1 \pm \sqrt{1-4C(x)}}{2C(x)}
\]

两个解，怎么办呢？

初中老师告诉我们：检验！

怎么检验？我们从 \([x^0]F(x) = 1\) 入手，可以发现这就是在 \(x = 0\) 的时候，\(F(x) = 1\)。

但是由于 \(C(x)\) 常数项为 \(0\)，且它在分母，所以显然有

\[\lim_{x \rightarrow 0} \frac{1 + \sqrt{1-4C(x)}}{2C(x)} = + \infty
\]

所以可以排除这个解了，但为了严谨，我们当然还要验证一下另一个解，但是另一个解的检验比较棘手，因为我们会得到一个 \(0\) 除以 \(0\) 的形式，这时候就需要用洛必达法则了（\(\leftarrow\) 戳它进入百度百科）

\[\lim_{x \rightarrow 0} \frac{1 - \sqrt{1-4C(x)}}{2C(x)} \\\\
= \lim_{x \rightarrow 0} \frac{1 - \sqrt{1-4x}}{2x} \\\\
= \lim_{x \rightarrow 0} \frac{\frac{\mathrm{d}(1 - \sqrt{1-4x})}{\mathrm{d}x}}{\frac{\mathrm{d}(2x)}{\mathrm{d}x}} \\\\
= 1
\]

（以上直接跳过求导过程，读者不妨仔细手算一下）正确了！

那么接下来搞一个多项式求逆、开方\(^*\)就好啦。

注意，上面的式子不能直接算，因为 \(C(x)\) 常数项为 \(0\)，不存在逆元！不过没关系，我们可以分子有理化一下：

\[\frac{1 - \sqrt{1-4C(x)}}{2C(x)} \\
= \frac{1 - (1 - 4C(x))}{2C(x) (1 + \sqrt{1 - 4C(x)})} \\
= \frac{2}{1 + \sqrt{1 - 4C(x)}}
\]

这样就可以直接求逆元啦！

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <algorithm>

using namespace std;

#define rep(i, s, t) for(int i = (s); i <= (t); i++)

#define dwn(i, s, t) for(int i = (s); i >= (t); i--)

const int BufferSize = 1 << 16;

char buffer[BufferSize], *Head, *Tail;

inline char Getchar() {

	if(Head == Tail) {

		int l = fread(buffer, 1, BufferSize, stdin);

		Tail = (Head = buffer) + l;

	}

	return *Head++;

}

int read() {

	int x = 0, f = 1; char c = Getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }

	return x * f;

}

#define maxn 524288

#define MOD 998244353

#define Groot 3

#define LL long long

int Pow(int a, int b) {

	int ans = 1, t = a;

	while(b) {

		if(b & 1) ans = (LL)ans * t % MOD;

		t = (LL)t * t % MOD; b >>= 1;

	}

	return ans;

}

int brev[maxn];

void FFT(int *a, int len, int tp) {

	int n = 1 << len;

	rep(i, 0, n - 1) if(i < brev[i]) swap(a[i], a[brev[i]]);

	rep(i, 1, len) {

		int wn = Pow(Groot, MOD - 1 >> i);

		if(tp < 0) wn = Pow(wn, MOD - 2);

		for(int j = 0; j < n; j += 1 << i) {

			int w = 1;

			rep(k, 0, (1 << i >> 1) - 1) {

				int la = a[j+k], ra = (LL)w * a[j+k+(1<<i>>1)] % MOD;

				a[j+k] = (la + ra) % MOD;

				a[j+k+(1<<i>>1)] = (la - ra + MOD) % MOD;

				w = (LL)w * wn % MOD;

			}

		}

	}

	if(tp < 0) rep(i, 0, n - 1) a[i] = (LL)a[i] * Pow(n, MOD - 2) % MOD;

	return ;

}

void Mul(int *A, int an, int *B, int bn) {

	int n = an + bn, N = 1, len = 0;

	while(N <= n) N <<= 1, len++;

	rep(i, 0, N - 1) brev[i] = (brev[i>>1] >> 1) | ((i & 1) << len - 1);

	FFT(A, len, 1); FFT(B, len, 1);

	rep(i, 0, N - 1) A[i] = (LL)A[i] * B[i] % MOD;

	FFT(A, len, -1);

	return ;

}

int tmp[maxn];

void inverse(int *f, int *g, int n) { // module x^n

	if(n == 1) return (void)(f[0] = Pow(g[0], MOD - 2));

	inverse(f, g, n + 1 >> 1);

	int N = 1, len = 0;

	while(N <= (n << 2)) N <<= 1, len++;

	rep(i, 0, N - 1) brev[i] = (brev[i>>1] >> 1) | ((i & 1) << len - 1);

	rep(i, n + 1 >> 1, N - 1) f[i] = 0; rep(i, 0, n - 1) tmp[i] = g[i]; rep(i, n, N - 1) tmp[i] = 0;

	FFT(f, len, 1); FFT(tmp, len, 1);

	rep(i, 0, N - 1) f[i] = (2ll - (LL)tmp[i] * f[i] % MOD + MOD) * f[i] % MOD;

	FFT(f, len, -1);

	rep(i, n, N - 1) f[i] = 0;

	return ;

}

int inv[maxn], _inv[maxn];

void p_sqrt(int *f, int *g, int n) { // g[0] = 1

	if(n == 1) return (void)(f[0] = 1);

	p_sqrt(f, g, n + 1 >> 1);

	rep(i, 0, (n + 1 >> 1) - 1) _inv[i] = (f[i] << 1) % MOD; rep(i, n + 1 >> 1, n - 1) _inv[i] = 0;

	inverse(inv, _inv, n);

	int N = 1, len = 0;

	while(N <= n + 1) N <<= 1, len++;

	rep(i, 0, N - 1) brev[i] = (brev[i>>1] >> 1) | ((i & 1) << len - 1);

	rep(i, n + 1 >> 1, N - 1) f[i] = 0; rep(i, 0, n - 1) tmp[i] = g[i]; rep(i, n, N - 1) tmp[i] = 0;

	FFT(f, len, 1); FFT(tmp, len, 1);

	rep(i, 0, N - 1) f[i] = (tmp[i] + (LL)f[i] * f[i]) % MOD;

	FFT(f, len, -1);

	rep(i, n, N - 1) f[i] = 0;

	Mul(f, n - 1, inv, n - 1);

	N = 1; while(N <= (n - 1 << 1)) N <<= 1;

	rep(i, n, N - 1) f[i] = 0;

	return ;

}

int num[50], cntn;

void putint(int x) {

	if(!x) return (void)puts("0");

	cntn = 0;

	while(x) num[++cntn] = x % 10, x /= 10;

	dwn(i, cntn, 1) putchar(num[i] + '0'); putchar('\n');

	return ;

}

int n, val[maxn], C[maxn], c[maxn];

int main() {

	int n = read(), m = read(), mxv = 0;

	rep(i, 1, n) val[i] = read(), mxv = max(mxv, val[i]);

	rep(i, 1, n) if(val[i] <= m) C[val[i]]++;

	rep(i, 1, m) C[i] = MOD - 4ll * C[i] % MOD; C[0] = 1;

	p_sqrt(c, C, m + 1); (c[0] += 1) %= MOD;

	inverse(C, c, m + 1);

	rep(i, 0, m) (C[i] <<= 1) %= MOD;

	rep(i, 1, m) putint(C[i]);

	return 0;

}

\(^*\)多项式开方，可以用前文（请翻到最后一题）的方法，但要用到多项式求 ln 和 exp，很麻烦，常数也大。这里我们可以利用一下开根的次数为 \(2\) 这个特殊性质优化一下。（以下多项式都省略后面的 \((x)\)）

还是考虑倍增，令 \(f_0^2 \equiv g (\mathrm{mod}\ x^{\lceil \frac{n}{2} \rceil})\)，用 \(f_0, g\) 表示出 \(f^2 \equiv g (\mathrm{mod}\ x^n)\) 的 \(f\)。

显然有

\[f - f_0 \equiv 0 (\mathrm{mod}\ x^{\lceil \frac{n}{2} \rceil})
\]

两边平方一下就好啦

\[(f - f_0)^2 \equiv 0 (\mathrm{mod}\ x^n) \\\\
f^2 - 2f_0f + f_0^2 \equiv 0 (\mathrm{mod}\ x^n) \\\\
g - 2f_0f + f_0^2 \equiv 0 (\mathrm{mod}\ x^n)
\]

于是得到

\[f \equiv \frac{g + f_0^2}{2f_0} (\mathrm{mod}\ x^n)
\]

巴特西

[codeforces438E]The Child and Binary Tree