首先我们需要找出一个朴素的递推来解决这个问题：
设状态$f(i)$表示权值和为$i$的二叉树的数量，$g(i)$表示权值$i$是否在集合中，即$g(i)=[iin S]$
枚举根节点和左子树的权值，立刻得到一个递推：
$f(n)=sum_{i=0}^{n}g(i)sum_{j=0}^{n-i}f(j)f(n-i-j)$
边界条件为$f(0)=1$（即认为没有节点的二叉树有一种，这样就包含了左右子树为空的情况）
那么发现最后那个转移是个卷积的形式，设$F(x)$为$f(i)$的生成函数，$G(x)$为$g(i)$的生成函数，那么有：$F(x)=G(x)F^{2}(x)+1$
为什么要加一？
因为很显然，$g(0)=0$，因此$G(x)$常数项为$0$，如果直接卷积的话得出的$F(x)$常数项是$0$，然而我们一开始规定$f(0)=1$，因此最后需要补充一个$1$
那么整理一下，就能得到：
$G(x)F(x)^{2}-F(x)+1=0$
这是一个关于$F(x)$的一元二次方程，解之得：
$F(x)=frac{1+ sqrt{1-4G(x)}}{2G(x)}$或$F(x)=frac{1-sqrt{1-4G(x)}}{2G(x)}$
由于分母常数项为$0$，不容易求逆，因此我们做一个分子有理化，得：
$F(x)=frac{1-[1-4G(x)]}{2G(x)[1-sqrt{1-4G(x)}]}$或$F(x)=frac{1-[1-4G(x)]}{2G(x)[1+sqrt{1-4G(x)}]}$
再整理一下，就得到：
$F(x)=frac{2}{1-sqrt{1-4G(x)}}$或$F(x)=frac{2}{1+sqrt{1-4G(x)}}$
那么是加号还是减号呢？
考虑$G(x)$常数项为0，$F(x)$常数项为1，可以看出应该取加号
那么我们最后的表达式就是$F(x)=frac{2}{1+sqrt{1-4G(x)}}$
直接多项式开根+多项式求逆即可
bzoj严重卡常，我用了unsigned int
代码：
#include <cstdio> #include <algorithm> #define uint unsigned int #define ll long long using namespace std; const uint mode=998244353; uint inv2=mode-mode/2; uint to[(1<<20)+5]; uint ig[(1<<20)+5],GF[(1<<20)+5]; uint G[(1<<20)+5],sG[(1<<20)+5],IG[(1<<20)+5],F[(1<<20)+5]; int n,m; inline uint MOD(uint x,uint y) { return x+y>=mode?x+y-mode:x+y; } inline uint pow_mul(uint x,uint y) { uint ret=1; while(y) { if(y&1)ret=(ll)(1ll*ret*x%mode); x=(ll)(1ll*x*x%mode),y>>=1; } return ret; } inline void NTT(uint *a,int len,int k) { for(register int i=0;i<len;++i)if(i<to[i])swap(a[i],a[to[i]]); for(register int i=1;i<len;i<<=1) { uint w0=pow_mul(3,(mode-1)/(i<<1)); for(register int j=0;j<len;j+=(i<<1)) { uint w=1; for(register int o=0;o<i;++o,w=(uint)(1ll*w*w0%mode)) { uint w1=a[j+o],w2=(uint)(1ll*a[j+o+i]*w%mode); a[j+o]=(w1+w2)%mode,a[j+o+i]=(w1-w2+mode)%mode; } } } if(k==-1) { uint inv=pow_mul(len,mode-2); for(int i=1;i<(len>>1);i++)swap(a[i],a[len-i]); for(int i=0;i<len;i++)a[i]=(uint)(1ll*a[i]*inv%mode); } } uint A[(1<<20)+5],B[(1<<20)+5],C[(1<<20)+5]; inline void mul(uint *f,uint *g,uint len) { int lim=1,l=0; while(lim<=2*len)lim<<=1,++l; for(register int i=0;i<lim;++i)to[i]=((to[i>>1]>>1)|((i&1)<<(l-1))),A[i]=B[i]=0; for(register int i=0;i<len;++i)A[i]=f[i],B[i]=g[i]; NTT(A,lim,1),NTT(B,lim,1); for(register int i=0;i<lim;++i)C[i]=(uint)(1ll*A[i]*B[i]%mode); NTT(C,lim,-1); } void get_inv(uint *f,uint *g,uint dep) { if(dep==1) { g[0]=pow_mul(f[0],mode-2); return; } int nxt=(dep+1)>>1; get_inv(f,g,nxt); int lim=1,l=0; while(lim<=2*dep)lim<<=1,l++; for(register int i=0;i<lim;++i)to[i]=((to[i>>1]>>1)|((i&1)<<(l-1))),A[i]=B[i]=0; for(register int i=0;i<dep;++i)A[i]=f[i],B[i]=g[i]; NTT(A,lim,1),NTT(B,lim,1); for(register int i=0;i<lim;++i)C[i]=(uint)(1ll*A[i]*B[i]%mode*B[i]%mode); NTT(C,lim,-1); for(register int i=0;i<dep;++i)g[i]=(2*g[i]+mode-C[i])%mode; } void get_sqr(uint *f,uint *g,int dep) { if(dep==1) { g[0]=1; return; } int nxt=(dep+1)>>1; get_sqr(f,g,nxt); for(register int i=0;i<dep;++i)ig[i]=0; get_inv(g,ig,dep); mul(g,g,dep); for(register int i=0;i<dep;++i)GF[i]=MOD(C[i],f[i]),ig[i]=(int)(1ll*ig[i]*inv2%mode); mul(GF,ig,dep); for(register int i=0;i<dep;++i)g[i]=C[i]; } inline int read() { int f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { n=read(),m=read(); for(register int i=1;i<=n;++i) { int x=read(); G[x]++; } for(register int i=1;i<=m;++i)G[i]=(uint)(mode-G[i]*4ll%mode); G[0]=1; m++; get_sqr(G,sG,m); sG[0]++; get_inv(sG,IG,m); for(register int i=1;i<m;++i)F[i]=(uint)(2ll*IG[i]%mode),printf("%u ",F[i]); return 0; }