1. 题目

传送门=￣ω￣=

2. 题解

OvO

翻前几天的代码发现了这个千年大坑 QwQ

咕咕咕了好几天了

做法还比较简单（然而我还是推了好久），可以说是多项式求逆开根模板了 OvO

首先不难想到，对 $C _ i$搞个生成函数 $P$

$P[C _ i]=1$

设多项式 $F$，$F _ i$表示权值为 $i$的神犇二叉树个数

根据二叉树的递归性质：

$F=F^2 \times P + 1$

其中 $F^2$表示左右儿子组合的各种情况，$P$是当前节点选哪个值，$+1$s 是因为当前这棵树可为空。

解方程得：

$F=\frac{1\pm \sqrt{1-4P}}{2P}$

酱紫看来有俩解，但其实只能取减号，因为 $P[0]=0$（也就是 $P$无常数项）

那么分母没有常数项，分子也必须不能有常数项才能做除法，否则没有意义。

因此分子的哪个 $1$必须被取减号后消掉（$1$为常数，$\sqrt {1-4P}$常数项为 $1$）。

所以 $F=\frac{1-\sqrt{1-4P}}{2P}$

分子分母同乘 $1+\sqrt{1-4P}$得：

$F=\frac{2P}{1+\sqrt{1-4P}}$

然后就没啦=￣ω￣=

代码：

#include <bits/stdc++.h>

#define NS (300005)
#define P (998244353)
#define G (3)
#define IV2 (499122177)

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int pls(int a, int b) {return a + b >= P ? a + b - P : a + b;}
int mns(int a, int b) {return a - b < 0 ? a - b + P : a - b;}
int mul(int a, int b) {return 1ll * a * b % P;}

int qpow(int a, int b)
{
    int res = 1; a %= P;
    while (b)
    {
        if (b & 1) res = mul(res, a);
        a = mul(a, a), b >>= 1;
    }
    return res;
}

int Inv(int a) {return qpow(a, P - 2);}

int n, m, p1[NS], sqp[NS], ivp[NS], rev[NS];

void NTT(int (&a)[NS], int N, int f)
{
    int bs = 0; while ((1 << bs) < N) bs++;
    for (int i = 1; i < N; i += 1)
    {
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bs - 1));
        if (i < rev[i]) swap(a[i], a[rev[i]]);
    }
    for (int l = 1; l < N; l <<= 1)
    {
        int G0 = qpow(G, (P - 1) / (l << 1));
        if (f == -1) G0 = Inv(G0);
        for (int i = 0; i < N; i += (l << 1))
        {
            int Gn = 1, t1, t2;
            for (int j = i; j < (i + l); j += 1, Gn = mul(Gn, G0))
            {
                t1 = a[j], t2 = mul(Gn, a[j + l]);
                a[j] = pls(t1, t2), a[j + l] = mns(t1, t2);
            }
        }
    }
    if (f == -1)
    {
        int Iv = Inv(N);
        for (int i = 0; i < N; i += 1) a[i] = mul(a[i], Iv);
    }
}

void Poly_Inv(int (&a)[NS], int (&b)[NS], int N)
{
    if (N == 1) {b[0] = Inv(a[0]); return;}
    Poly_Inv(a, b, N >> 1);
    static int t[NS];
    memmove(t, a, sizeof(int) * N), memset(t + N, 0, sizeof(int) * N);
    NTT(t, N << 1, 1), NTT(b, N << 1, 1);
    for (int i = 0; i < (N << 1); i += 1)
        b[i] = mns(mul(b[i], 2), mul(t[i], mul(b[i], b[i])));
    NTT(b, N << 1, -1), memset(b + N, 0, sizeof(int) * N);
}

void Poly_Sqrt(int (&a)[NS], int (&b)[NS], int N)
{
    if (N == 1) {b[0] = 1; return;} // Because of b[0] = sqrt a[0] = 1
    Poly_Sqrt(a, b, N >> 1);
    static int t1[NS], t2[NS];
    memmove(t1, a, sizeof(int) * N), memset(t1 + N, 0, sizeof(int) * N);
    memset(t2, 0, sizeof(int) * N * 2), Poly_Inv(b, t2, N);
    NTT(t1, N << 1, 1), NTT(t2, N << 1, 1), NTT(b, N << 1, 1);
    for (int i = 0; i < (N << 1); i += 1)
        b[i] = mul(pls(mul(b[i], b[i]), t1[i]), mul(IV2, t2[i]));
    NTT(b, N << 1, -1), memset(b + N, 0, sizeof(int) * N);
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m), p1[0] = 1;
    for (int i = 1, a; i <= n; i += 1)
    {
        IN(a);
        if (a <= m) p1[a] = mns(0, 4);
    }
    int N = 1; while (N <= m) N <<= 1;
    Poly_Sqrt(p1, sqp, N), sqp[0] = pls(sqp[0], 1), Poly_Inv(sqp, ivp, N);
    for (int i = 1; i <= m; i += 1) printf("%d\n", mul(ivp[i], 2));
    return 0;
}