Codeforces

Luogu

分析

设 $s_i$ 表示 $i$ 是否在集合中，$f_i$ 表示权值和为 $i$ 的二叉树数量，那么
$$
f_n=\begin{cases}1,&n=0\\\sum_{i=1}^ns_i\sum_{j=0}^{n-i}f_jf_{n-i-j},&n\geq 1\end{cases}
$$
设 $s_i$ 的 OGF 为 $S(x)$，$f_i$ 的 OGF 为 $F(x)$，那么
$$
F(x)=S(x)F(x)^2+1
$$
解得
$$
F(x)=\frac{1\pm\sqrt{1-4S(x)}}{2S(x)}
$$
然而 $S(x)$ 常数项可能是 $0$，所以把根式除掉下面去
$$
F(x)=\frac{2}{1\pm\sqrt{1-4S(x)}}
$$
因为 $[x^0]F(x)=1,[x^0]S(x)=1$，代进去可以知道下面应该取 $+$，所以
$$
F(x)=\frac{2}{1+\sqrt{1-4S(x)}}
$$
多项式开根+多项式求逆即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=262144+10;
const int mod=998244353,inv2=499122177;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int r[N];
void NTT(int* A,int n,int op) {
    for (int i=0;i<n;++i) if (i<r[i]) swap(A[i],A[r[i]]);
    for (int i=1;i<n;i<<=1) {
        int rot=qpow(op==1?3:332748118,(mod-1)/(i<<1));
        for (int j=0;j<n;j+=i<<1)
            for (int k=0,w=1;k<i;++k,w=1ll*w*rot%mod) {
                int x=A[j+k],y=1ll*w*A[j+k+i]%mod;
                A[j+k]=(x+y)%mod,A[j+k+i]=(x-y+mod)%mod;
            }
    }
    if (op==-1) { int inv=qpow(n,mod-2);
        for (int i=0;i<n;++i) A[i]=1ll*A[i]*inv%mod;
    }
}
int NTT_init(int n) {
    int lim=1,l=-1;
    for (;lim<=n;lim<<=1,++l);
    for (int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<l);
    return lim;
}

void getinv(int* F,int* G,int n) {
    static int A[N],B[N];
    if (n==1) { G[0]=qpow(F[0],mod-2); return; }
    getinv(F,G,n>>1);
    for (int i=0;i<n;++i) A[i]=F[i],B[i]=G[i];
    int lim=NTT_init(n);
    NTT(A,lim,1),NTT(B,lim,1);
    for (int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod*B[i]%mod;
    NTT(A,lim,-1);
    for (int i=0;i<n;++i) G[i]=(2ll*G[i]-A[i]+mod)%mod;
    for (int i=0;i<lim;++i) A[i]=B[i]=0;
}

void getsqrt(int* F,int* G,int n) {
    static int A[N],B[N];
    if (n==1) { G[0]=1; return; }
    getsqrt(F,G,n>>1);
    for (int i=0;i<n;++i) A[i]=F[i];
    getinv(G,B,n);
    int lim=NTT_init(n);
    NTT(A,lim,1),NTT(B,lim,1);
    for (int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod;
    NTT(A,lim,-1);
    for (int i=0;i<n;++i) G[i]=1ll*(A[i]+G[i])*inv2%mod;
    for (int i=0;i<lim;++i) A[i]=B[i]=0;
}

int n,m,S[N],G[N],F[N];

int main() {
    n=read(),m=read();
    for (int i=1;i<=n;++i) S[read()]=1;
    int lim=1,l=-1;
    for (;lim<=m;lim<<=1,++l);
    for (int i=1;i<=m;++i) S[i]=(mod-4*S[i])%mod;
    ++S[0]; getsqrt(S,G,lim);
    ++G[0]; getinv(G,F,lim);
    for (int i=1;i<=m;++i) F[i]=2ll*F[i]%mod;
    for (int i=1;i<=m;++i) printf("%d\n",F[i]);
    return 0;
}