CF438E

The Child and Binary Tree

令 $f_i$ 表示权值和为 $i$ 的神犇二叉树个数。方便起见令 $f_0=1$。

令 $g_i$ 表示权值 $i$ 是否在集合 $c$ 中，即 $g_i=[i\in c]$。

我们可以先作 DP：

$$
f_n=
\begin{cases}
1 & n=0
\\
\sum_{i=0}^{n}g_i\sum_{j=0}^{n-i}f_jf_{n-i-j} & n>0
\end{cases}
$$

这个转移的意思就是抽出一个顶点，其权值合法，然后枚举它左右子树的合法形态。

很显然这是一个卷积形式的东西，我们转化成生成函数：

$$F(x)=1+G(x)F(x)^2$$

解一下：

$$F(x)=\dfrac{1\pm \sqrt{1-4G(x)}}{2G(x)}$$

取负号时才收敛，因此：

$$F(x)=\dfrac{1-\sqrt{1-4G(x)}}{2G(x)}$$

其实这样就可以算了，但是我们可以通过化简提高效率，上下同时乘上 $1+\sqrt{1-4G(x)}$：

$$F(x)=\dfrac{2}{1+\sqrt{1-4G(x)}}$$

这样只要做一次开根和一次求逆。

懒了，把全家桶粘过来艹过去了。

时间复杂度 $O(m\log m)$。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
#define Clr(f,n) memset(f,0,sizeof(ll)*(n))
#define Cpy(f,g,n) memcpy(f,g,sizeof(ll)*(n))
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writes(ll x) {write(x);putchar(32);}
inline void writeln(ll x) {write(x);putchar(10);}

const ll N=2e5,mo=998244353ll,G=3;

namespace Aeft{
  inline ll Pow(ll b,ll p) {
    ll res=1;while(p) {if(p&1) res=res*b%mo;b=b*b%mo;p>>=1;}return res;
  }
}using Aeft::Pow;

const ll invG=Pow(G,mo-2);

ll n,m;
ll rev[N*2+5],g[N*2+5],inv[N+5];

// NTT.
inline void Prev(ll n) {
  for(ll i=0;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)?(n>>1):0);
}
inline void NTT(ll *f,ll n,bool op) {
  Prev(n);for(ll i=0;i<n;i++) if(i<rev[i]) swap(f[i],f[rev[i]]);
  for(ll p=2;p<=n;p<<=1) {
    ll len=p>>1,tG=Pow(op?invG:G,(mo-1)/p);
    for(ll k=0;k<n;k+=p) {
      for(ll l=k,buf=1;l<k+len;l++,buf=buf*tG%mo) {
        ll t=f[l+len]*buf%mo;
        f[l+len]=f[l]-t;if(f[l+len]<0) f[l+len]+=mo;
        f[l]+=t;if(f[l]>mo) f[l]-=mo;
      }
    }
  }
  if(op) {ll invn=Pow(n,mo-2);for(ll i=0;i<n;i++) f[i]=f[i]*invn%mo;}
}
inline void Conv(ll *f,ll *g,ll n) {for(ll i=0;i<n;i++) f[i]=f[i]*g[i]%mo;}
inline void Times(ll *f,ll *g,ll len,ll lim) {
  static ll sav[N*2+5];ll n=1;for(;n<len+len;n<<=1);
  Clr(sav,n);Cpy(sav,g,n);NTT(f,n,0);NTT(sav,n,0);
  Conv(f,sav,n);NTT(f,n,1);Clr(f+lim,n-lim);Clr(sav,n);
}

// Inversion
inline void Invp(ll *f,ll m) {
  ll n;for(n=1;n<m;n<<=1);
  static ll w[N*2+5],r[N*2+5],tmp[N*2+5];
  w[0]=Pow(f[0],mo-2);
  for(ll len=2;len<=n;len<<=1) {
    for(ll i=0;i<(len>>1);i++) r[i]=(w[i]<<1)%mo;
    Cpy(tmp,f,len);NTT(w,len<<1,0);Conv(w,w,len<<1);
    NTT(tmp,len<<1,0);Conv(w,tmp,len<<1);
    NTT(w,len<<1,1);Clr(w+len,len);
    for(ll i=0;i<len;i++) w[i]=(r[i]-w[i]+mo)%mo;
  }
  Cpy(f,w,m);Clr(tmp,n<<1);Clr(w,n<<1);Clr(r,n<<1);
}

// Newton Iteration.
inline void Deriv(ll *f,ll m) {
  for(ll i=1;i<m;i++) {f[i-1]=f[i]*i%mo;}f[m-1]=0;
}
inline void Integr(ll *f,ll m) {
  for(ll i=m;i;i--) {f[i]=f[i-1]*inv[i]%mo;}f[0]=0;
}
inline void Init(ll n) {
  inv[1]=1;for(ll i=2;i<=n;i++) inv[i]=inv[mo%i]*(mo-mo/i)%mo;
}

// Squre root
inline void Sqroot(ll *f,ll m) {
  ll n;for(n=1;n<m;n<<=1);static ll b1[N*2+5],b2[N*2+5];b1[0]=1;
  for(ll len=2;len<=n;len<<=1) {
    for(ll i=0;i<(len>>1);i++) b2[i]=(b1[i]<<1)%mo;
    Invp(b2,len);NTT(b1,len,0);Conv(b1,b1,len);NTT(b1,len,1);
    for(ll i=0;i<len;i++) b1[i]=(f[i]+b1[i])%mo;
    Times(b1,b2,len,len);
  }
  Cpy(f,b1,m);Clr(b1,n+n);Clr(b2,n+n);
}

// Division with Remainder. Here f/g->f f%g->g.
// The quotient is the Prev n-m+1 terms of f.
// The remainder is the Prev m-1 terms of g.
inline void Rev(ll *f,ll n) {
  for(ll i=0;(i<<1)<n-1;i++) swap(f[i],f[n-i-1]);
}
inline void Divid(ll *f,ll *g,ll n,ll m) {
  static ll q[N<<1],t[N<<1];ll l=n-m+1;
  Rev(g,m);Cpy(q,g,l);Rev(g,m);Rev(f,n);Cpy(t,f,l);Rev(f,n);
  Invp(q,l);Times(q,t,l,l);Rev(q,l);Times(g,q,n,n);
  for(ll i=0;i<m-1;i++) {g[i]=(f[i]-g[i]+mo)%mo;}
  Clr(g+m-1,l);Cpy(f,q,l);Clr(f+l,n-l);
}

// Ln & Exp.
inline void Lnp(ll *f,ll m) {
  static ll g[N*2+5];
  Cpy(g,f,m);Invp(g,m);Deriv(f,m);Times(f,g,m,m);
  Integr(f,m-1);Clr(g,m);
}
inline void Exp(ll *f,ll m) {
  static ll s[N*2+5],s2[N*2+5];ll n=1;for(;n<m;n<<=1);s2[0]=1;
  for(ll len=2;len<=n;len<<=1) {
    Cpy(s,s2,len>>1);Lnp(s,len);
    for(ll i=0;i<len;i++) {s[i]=(f[i]-s[i]+mo)%mo;}
    s[0]=(s[0]+1)%mo;Times(s2,s,len,len);
  }
  Cpy(f,s2,m);Clr(s,n);Clr(s2,n);
}

int main() {

  n=read()+1;m=read()+1;
  for(ll i=1;i<n;i++) {ll x=read();g[x]=-4;}g[0]=1;
  
  Sqroot(g,m);g[0]++;Invp(g,m);

  for(ll i=0;i<m;i++) g[i]=g[i]*2ll%mo;

  for(ll i=1;i<m;i++) writeln(g[i]);

  return 0;
}