CF438E 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_n=\sum_{i=1}^n g_i \sum_{j=1}^{n-i} f_j f_{n-i-j}\quad (n > 0) \] 记 \(F(x)\) 为 \(f_i\) 的生成函数，\(G(x)\) 为 \(g_i\) 的生成函数，则上式可写作 \[ F = G * F^2+1 \] 利用求根公式可得 \[ F=\frac{1 \pm \sqrt{1-4 G}}{2 G} \] 注意到取正号时 \(F\) 形式上不收敛，即 \(\lim\limits_{x \to 0} =\infty\) ，取负号的情况 \(F=\frac{1 - \sqrt{1-4 G}}{2 G}\) 即可

进一步化简得到 \[ F=\frac{2}{1+\sqrt{1-4 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;
}