CF438E The Child and Binary Tree 题解
题目链接：The Child and Binary Tree
题意：
cxy 很喜欢计算机科学，而且尤其喜欢二叉树。 考虑一个含有 $n$ 个互异正整数的序列 $c_1,c_2\cdots,c_n$。如果一棵带点权的有根二叉树满足其所有顶点的权值都在集合 $\{c_1,c_2,\cdots,c_n\}$ 中，cxy 就会将其称作神犇的。
并且她认为，一棵带点权的树的权值，是其所有顶点权值的总和。
给出一个整数 $m$，你能对于任意的 $1\leq s\leq m$ 计算出权值为 $s$ 的神犇二叉树的个数吗？
我们只需要知道答案关于 $998244353$ 取模后的值。
参照下图以更好的理解什么样的两棵二叉树会被视为不同的。
输入格式：
输入第一行有 $2$ 个整数 $n,m$ $(1\leq n,m\leq 10^5)$。 第二行有 $n$ 个用空格隔开的互异的整数 $c_1,c_2\cdots,c_n$ $(1\le c_i\le10^5)$。
输出格式：
输出 $m$ 行，每行有一个整数。第 $i$ 行应当含有权值恰为 $i$ 的神犇二叉树的总数。请输出答案关于 $998244353$ 取模的结果。
非常有趣的题目。设 $f_i$ 表示点权和为 $i$ 的二叉树的个数，$g_i$ 为权值 $i$ 在 $c$ 中的出现次数。
边界 $f_0 = 1, g_0 = 1$ 。转移考虑钦定当前位选什么，则
记 $F(x)$ 为 $f_i$ 的生成函数，$G(x)$ 为 $g_i$ 的生成函数，则上式可写作
利用求根公式可得
注意到取正号时 $F$ 形式上不收敛，即 $\lim\limits_{x \to 0} =\infty$ ，取负号的情况 $F=\frac{1 - \sqrt{1-4 G}}{2 G}$ 即可
进一步化简得到
考虑多项式开根+求逆。
时间复杂度 $\mathcal{O}(n \log n)$
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(4e5 + 15))
namespace NTT
{
const int P = 998244353;
const int G = 3, Gi = 332748118;
#define NTT_N (N * 4)
void add(int &x, int y) { (x += y) >= P ? x -= P : 0; }
int qpow(int a, int b)
{
int r = 1;
for(a %= P; b; b >>= 1, a = a * a % P)
if(b & 1) r = r * a % P;
return r;
}
int c[NTT_N], d[NTT_N], r[NTT_N];
void NTT(int *A, int limit, int type)
{
for(int i = 0; i < limit; i++)
if(i < r[i]) swap(A[i], A[r[i]]);
for(int mid = 1; mid < limit; mid *= 2)
{
int Wn = qpow((type == 1 ? G : Gi), (P - 1) / (mid * 2));
for(int j = 0; j < limit; j += (mid * 2))
{
int w = 1;
for(int k = 0; k < mid; k++, w = (w * Wn) % P)
{
int x = A[j + k], y = w * A[j + k + mid] % P;
A[j + k] = (x + y) % P; A[j + k + mid] = (x - y + P) % P;
}
}
}
if(type == -1)
{
int Inv = qpow(limit, P - 2);
for(int i = 0; i < limit; i++) A[i] = A[i] * Inv % P;
}
}
void Inv(int n, int *a, int *b)
{
if(n == 1) { b[0] = qpow(a[0], P - 2); return; }
Inv((n + 1) / 2, a, b);
int l = 0, limit = 1;
for(; limit <= (n - 1) * 2; l++, limit *= 2);
for(int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
for(int i = 0; i < n; i++) c[i] = a[i];
for(int i = n; i < limit; i++) c[i] = 0;
NTT(c, limit, 1); NTT(b, limit, 1);
for(int i = 0; i < limit; i++)
b[i] = (2 - c[i] * b[i] % P + P) % P * b[i] % P;
NTT(b, limit, -1);
for(int i = n; i < limit; i++) b[i] = 0;
}
void Sqrt(int n, int *a, int *b)
{
if(n == 1) { b[0] = 1; return; }
Sqrt((n + 1) / 2, a, b);
int l = 0, limit = 1;
for(; limit <= (n - 1) * 2; l++, limit *= 2);
for(int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1 | ((i & 1) << (l - 1)));
for(int i = 0; i < limit; i++) d[i] = 0;
Inv(limit / 2, b, d);
for(int i = 0; i < n; i++) c[i] = a[i];
for(int i = n; i < limit; i++) c[i] = 0;
NTT(c, limit, 1); NTT(d, limit, 1);
for(int i = 0; i < limit; i++) c[i] = c[i] * d[i] % P;
NTT(c, limit, -1);
static int inv2 = qpow(2, P - 2);
for(int i = 0; i < n; i++) b[i] = (b[i] + c[i]) % P * inv2 % P;
for(int i = n; i < limit; i++) b[i] = 0;
}
};
using NTT::P; using NTT::add;
int f[N], g[N], t[N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int n, m; cin >> n >> m;
rep(i, 1, n) { int x; cin >> x; add(g[x], 1); }
rep(i, 1, m) { g[i] = P - 4 * g[i] % P; }
add(g[0], 1); NTT::Sqrt(m + 1, g, t);
add(t[0], 1); NTT::Inv(m + 1, t, f);
rep(i, 0, m) add(f[i], f[i]);
rep(i, 1, m) cout << f[i] << '\n';
return 0;
}参考文献：
