题目大意：给一个集合$S(|S|leqslant10^5)$；问任意点数，每个点权值$in S$，并且权值和为$d$的无标号有根二叉树的个数，对于$din[1,m](mleqslant10^5)$的每一个$d$输出答案
题解：枚举根，令$f_n$表示权值和为$n$的二叉树个数，$c_i=[iin S]$，枚举根的权值可以得出$DP$式子：$f_n=sumlimits_{i=1}^nc_isumlimits_{j=0}^{n-i}f_j imes f_{n-i-j},f_0=1$。
令$F(x)$为$f$的生成函数，$C(x)$为$c$的生成函数，$F(x)=C(x)*F(x)^2+1$。
所以$C(x)*F(x)^2-F(x)+1=0$，所以$F(x)=dfrac{1pmsqrt{1-4C(x)}}{2C(x)}$，因为$2C(x)$常数项为$0$，若分子取加号，常数项不为$0$，不可以除，所以取负号，这样分子的常数项也为$0$。
发现$2C(x)$常数项为$0$，不可以求逆，考虑转化一下
$$
egin{align*}
F(x)&=dfrac{1-sqrt{1-4C(x)}}{2C(x)}\
&=dfrac{(1-sqrt{1-4C(x)})(1+sqrt{1-4C(x)})}{2C(x)(1+sqrt{1-4C(x)})}\
&=dfrac{2}{1+sqrt{1-4C(x)}}\
end{align*}
$$
就好了
卡点：无
C++ Code：
#include <algorithm>
#include <cstdio>
#include <iostream>
#define maxn 262144
const int mod = 998244353, half = (mod + 1) / 2;
#define mul(x, y) static_cast<long long> (x) * (y) % mod
namespace Math {
inline int pw(int base, int p) {
static int res;
for (res = 1; p; p >>= 1, base = mul(base, base)) if (p & 1) res = mul(res, base);
return res;
}
inline int inv(int x) { return pw(x, mod - 2); }
}
inline void reduce(int &x) { x += x >> 31 & mod; }
inline void clear(register int *l, const int *r) {
if (l >= r) return ;
while (l != r) *l++ = 0;
}
namespace Poly {
#define N maxn
int lim, s, rev[N], Wn[N];
inline void init(const int n) {
lim = 1, s = -1; while (lim < n) lim <<= 1, ++s;
for (register int i = 1; i < lim; ++i) rev[i] = rev[i >> 1] >> 1 | (i & 1) << s;
const int t = Math::pw(3, (mod - 1) / lim);
*Wn = 1; for (register int *i = Wn + 1; i != Wn + lim; ++i) *i = mul(*(i - 1), t);
}
inline void FFT(int *A, const int op = 1) {
for (register int i = 1; i < lim; ++i) if (i < rev[i]) std::swap(A[i], A[rev[i]]);
for (register int mid = 1; mid < lim; mid <<= 1) {
const int t = lim / mid >> 1;
for (register int i = 0; i < lim; i += mid << 1)
for (register int j = 0; j < mid; ++j) {
const int X = A[i + j], Y = mul(A[i + j + mid], Wn[t * j]);
reduce(A[i + j] += Y - mod), reduce(A[i + j + mid] = X - Y);
}
}
if (!op) {
const int ilim = Math::inv(lim);
for (register int *i = A; i != A + lim; ++i) *i = mul(*i, ilim);
std::reverse(A + 1, A + lim);
}
}
void INV(int *A, int *B, int n) {
if (n == 1) { *B = Math::inv(*A); return ; }
const int len = n + 1 >> 1;
static int C[N], D[N];
INV(A, B, len), init(len * 3);
std::copy(A, A + n, C); clear(C + n, C + lim);
std::copy(B, B + len, D), clear(D + len, D + lim);
FFT(C), FFT(D);
for (int i = 0; i < lim; ++i) D[i] = (2 - mul(D[i], C[i]) + mod) * D[i] % mod;
FFT(D, 0); std::copy(D + len, D + n, B + len);
}
void SQRT(int *A, int *B, int n) {
if (n == 1) { *B = 1; return ; }
const int len = n + 1 >> 1;
static int C[N], D[N];
SQRT(A, B, len);
INV(B, D, n), clear(D + n, D + lim);
std::copy(A, A + n, C); clear(C + n, C + lim);
FFT(C), FFT(D);
for (int i = 0; i < lim; ++i) D[i] = mul(D[i], C[i]) * half % mod;
FFT(D, 0); std::copy(D + len, D + n, B + len);
}
void TANG_Yx(int *A, int *B, int n) {
static int C[N], D[N];
*D = 1; for (int i = 1; i < n; ++i) reduce(D[i] = -mul(4, A[i]));
SQRT(D, C, n);
reduce(*C += 1 - mod);
INV(C, D, n);
for (int i = 0; i < n; ++i) reduce(B[i] = D[i] + D[i] - mod);
}
#undef N
}
int n, m;
int cnt[maxn], f[maxn];
int main() {
std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
std::cin >> n >> m;
for (int i = 0, x; i < n; ++i) {
std::cin >> x;
cnt[x] = 1;
}
Poly::TANG_Yx(cnt, f, m + 1);
for (int i = 1; i <= m; ++i) std::cout << f[i] << '
';
return 0;
}