思路
看到计数和\(998244353\)，可以感觉到这是一个DP+生成函数+NTT的题。
设\(s_i\)表示\(i\)是否在集合中，\(A\)为\(s\)的生成函数，即\(A(x)=\sum_n s_nx^n\)。
设\(f_n\)为有\(n\)分时二叉树的个数。
考虑枚举左子树大小和根节点权值，得到
\[f_n=[n=0]+\sum_{i=1}^{mx} s_i \sum_{j=0}^{n-i} f_jf_{n-i-j}
\]
\]
然后记\(F(x)\)为\(f\)的生成函数：
\[\begin{align*}
F(x)&=\sum_n f_nx^n\\
&=1+\sum_n x^n\sum_{i=1}^{mx} s_i \sum_{j=0}^{n-i} f_jf_{n-i-j}
\end{align*}
\]
F(x)&=\sum_n f_nx^n\\
&=1+\sum_n x^n\sum_{i=1}^{mx} s_i \sum_{j=0}^{n-i} f_jf_{n-i-j}
\end{align*}
\]
可以发现\((i)+(j)+(n-i-j)=n\)，即后面是三个多项式卷积在一起，得到\(F=1+A*F^2\)。
利用求根公式得到\(F=\frac{1\pm \sqrt{1-4A}}{2A}\)。
用某种奇怪的理论得到只能取减号，于是有
\[F=\frac{1-\sqrt{1-4A}}{2A}
\]
\]
似乎做完了，但你会发现下面\(2A\)的常数项为\(0\)，好像不能多项式求逆。（也许可以？大佬能教我一下吗？）
update：已经学会如何求逆，将其放在最后。
怎么办呢？我们可以把这个式子再化一下：
\[F=\frac{1-\sqrt{1-4A}}{2A}=\frac{2}{1+\sqrt{1-4A}}
\]
\]
此时开根和求逆都没有问题，可以做了。
代码
#include<bits/stdc++.h>
namespace my_std{
using namespace std;
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,x,y) for (int i=(x);i>=(y);i--)
#define go(x) for (int i=head[x];i;i=edge[i].nxt)
#define sz 404040
#define mod 998244353
typedef long long ll;
template<typename T>
inline void read(T& t)
{
t=0;char f=0,ch=getchar();
double d=0.1;
while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
if(ch=='.')
{
ch=getchar();
while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();
}
t=(f?-t:t);
}
template<typename T,typename... Args>
inline void read(T& t,Args&... args){read(t); read(args...);}
void file()
{
#ifndef ONLINE_JUDGE
freopen("a.txt","r",stdin);
#endif
}
// inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;
ll ksm(ll x,int y)
{
ll ret=1;
for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;
return ret;
}
ll inv(ll x){return ksm(x,mod-2);}
int limit,r[sz];
ll G[sz],_G[sz];
void init(){for (int mid=1;mid<sz;mid<<=1) _G[mid]=inv(G[mid]=ksm(3,(mod-1)/mid>>1));}
void NTT_init(int n)
{
limit=1;int l=-1;
while (limit<=n+n) limit<<=1,++l;
rep(i,0,limit-1) r[i]=(r[i>>1]>>1)|((i&1)<<l);
}
void NTT(ll *a,int type)
{
rep(i,0,limit-1) if (i<r[i]) swap(a[i],a[r[i]]);
rep(i,0,limit-1) a[i]%=mod;
for (int mid=1;mid<limit;mid<<=1)
{
ll Wn=(type==1)?G[mid]:_G[mid];
for (int j=0,len=mid<<1;j<limit;j+=len)
{
ll w=1;
for (int k=0;k<mid;k++,w=w*Wn%mod)
{
ll x=a[j+k],y=a[j+k+mid]*w;
a[j+k]=(x+y)%mod;a[j+k+mid]=(1ll*mod*mod-y+x)%mod;
}
}
}
if (type==1) return;
ll I=inv(limit);
rep(i,0,limit-1) a[i]=a[i]*I%mod;
}
ll tmp1[sz],tmp2[sz],tmp3[sz],tmp4[sz];
void PolyInv(ll *a,ll *f,int n) // f=a^{-1}
{
if (n==1) return (void)(f[0]=inv(a[0]));
int mid=(n+1)>>1;
PolyInv(a,f,mid);
NTT_init(n);
rep(i,0,mid-1) tmp1[i]=f[i];rep(i,mid,limit-1) tmp1[i]=0;
rep(i,0,n-1) tmp2[i]=a[i];rep(i,n,limit-1) tmp2[i]=0;
NTT(tmp1,1);NTT(tmp2,1);
rep(i,0,limit-1) tmp1[i]=tmp1[i]*(mod+2-tmp1[i]*tmp2[i]%mod)%mod;
NTT(tmp1,-1);
rep(i,0,n-1) f[i]=tmp1[i];
rep(i,0,limit-1) tmp1[i]=tmp2[i]=0;
}
void PolySqrt(ll *a,ll *f,int n)
{
if (n==1) return (void)(f[0]=sqrt(a[0])+0.5);
int mid=(n+1)>>1;
PolySqrt(a,f,mid);
PolyInv(f,tmp3,n);
rep(i,0,n-1) tmp1[i]=a[i],tmp2[i]=f[i];
NTT_init(n);
NTT(tmp1,1);NTT(tmp2,1);NTT(tmp3,1);
ll inv2=inv(2);
rep(i,0,limit-1) tmp1[i]=inv2*(tmp1[i]*tmp3[i]%mod+tmp2[i])%mod;
NTT(tmp1,-1);
rep(i,0,n-1) f[i]=tmp1[i];
rep(i,0,limit-1) tmp1[i]=tmp2[i]=tmp3[i]=0;
}
int n,m;
ll a[sz];
ll tt1[sz],tt2[sz];
ll ans[sz];
int main()
{
file();
init();
read(n,m);
int x;
rep(i,1,n) read(x),a[x]=1;
tt1[0]=1;rep(i,1,m) tt1[i]=mod-4*a[i]%mod;
PolySqrt(tt1,tt2,m+1);
++tt2[0];
PolyInv(tt2,ans,m+1);
rep(i,1,m) ans[i]=ans[i]*2%mod;
rep(i,1,m) printf("%lld\n",ans[i]);
return 0;
}
更新
前文说到不知道怎么多项式求逆，现在学会了更新一发。
考虑到你推出的式子肯定是正确的（不正确我也没办法），那么下面多出来的那些\(x^n\)肯定可以被上面消掉，否则就没法做了。
那么可以先把\(\min\{a_i\}\)（记作\(mn\)）提出来，然后给下面求逆。然后上面开完根之后整体除一个\(x^{mn}\)即可。
然而这样会有一些奇怪的事情发生：原来全都对\(x^{m+1}\)取模，现在要搞一些事情，对\(x^{\max(m,\max\{a_i\})+mn+1}\)取模。（或者你懒的话直接对\(x^{200000}\)取模也可以）
这样常数会大一些，但也可以通过。
代码：（只有主函数）
int n,m;
ll a[sz];int mn=1e9,mx;
ll tt1[sz],sqr[sz],tt2[sz],inva[sz];
ll ans[sz];
int main()
{
file();
init();
read(n,m);
int x;
rep(i,1,n) read(x),a[x]=1,mn=min(mn,x),mx=max(mx,x);
mx=max(mx,m);
tt1[0]=1;rep(i,1,mx) tt1[i]=(mod-4*a[i])%mod;
rep(i,0,mx) tt2[i]=2*a[i+mn];
PolySqrt(tt1,sqr,mx+1+mn);
PolyInv(tt2,inva,mx+1);
rep(i,0,mx) sqr[i]=(mod-sqr[i+mn])%mod;
NTT_init(mx+1);
rep(i,mx+1,limit-1) sqr[i]=inva[i]=0;
NTT(inva,1);NTT(sqr,1);
rep(i,0,limit-1) ans[i]=inva[i]*sqr[i]%mod;
NTT(ans,-1);
rep(i,1,m) printf("%lld\n",ans[i]);
return 0;
}