幼儿园，是这个幼儿园吗？
众所周知PB大佬写过题解的题，整个机房都要再写一遍（bushi）
新手表示满脑子只有 (DP) ……
设一个憨批数组 (s) ，值只有 (0/1) 第 (i) 位表示 (i) 这个数字是否合法
首先找到 (dp) 方程： (f_n=sum{s_isum{f_{n-j-i}f_{j}}})
同时知道 (f_0=1)
嗯，看起来很好吃
然后我们设 (f) 的生成函数为 (F(x)=sum{f_ix^i})
设 (s) 的生成函数是 (G(x)=sum{s_ix^i})
我们规定常数项为 (0) ,因为原题中给定的合法数大于 (0) ((forall i,s_i>0))
那么每一项就是
[F_i=sumlimits_{j=1}^{j<=i}{s_jsumlimits_{k=0}^{k<=i-j}{F_{i-j-k}*F_{k}}}
]
[F=1+G*F^2
]
然后考虑化简，题解有人对直接求根表示质疑，我觉得他的证明非常好，值得学习
[GF=F^2G^2+G
]
[0=F^2G^2-GF+G
]
[0=(FG+frac{1}{2})^2-frac{1}{4}+G
]
[frac{1}{4}-G=(GF-frac{1}{2})^2
]
[1-4G=4(GF-frac{1}{2})
]
然后因为左式的常数项不是 (0) 了，我们可以开根
[-sqrt[2]{1-4G}=2(GF-frac{1}{2})
]
考虑到我们还有个 (GF) ，这个小家伙的常数项必为 (0) ((GF_0=G_0*F_0))
如果我们选择了正，那么左式的常数项就不为 (0) 所以我们必须得选择取负
[frac{1-sqrt[2]{1-4G}}{2}=GF
]
初一数学，上下同乘 (1+sqrt[2]{1-4G}) ，于是原式就被化简成了
[F=frac{2}{1+sqrt[2]{1-4G}}
]
是的是的我跳步了不过这步不难
然后让我们冲！
(代码一如既往地加了些许常数优化啊~)
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const ll mod=998244353,g=3,N=8e5+10,inv2=499122177;
ll aa[N],bb[N],ans[N];
static inline ll ksm(ll x,ll k,ll tmp=1){
while(k){
if(k&1)tmp=tmp*x%mod;
x=x*x%mod,k>>=1;
}
return tmp;
}
namespace NTT{
ll rev[N];
static inline ll pre(ll n,ll m,ll l=0){
while((1<<l)<=n+m)l++;
for(ll i=0;i<(1<<l);i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
return l;
}
inline void Ntt(ll *f,ll inv,ll li){
for(ll i=0;i<li;i++)if(i<rev[i])swap(f[i],f[rev[i]]);
for(ll mid=1;mid<li;mid<<=1){
ll tmp=ksm(g,(mod-1)/(mid*2));
ll tp=mid<<1;
if(inv==-1)tmp=ksm(tmp,mod-2);
for(ll i=0;i<li;i+=tp){
ll w=1;
for(register ll x,y,j=0;j<mid;j++,w=w*tmp%mod){
x=f[i+j],y=f[i+j+mid]*w%mod;
f[i+j]=(x+y)%mod,f[i+j+mid]=(x-y+mod)%mod;
}
}
}
if(inv==-1){
ll t=ksm(li,mod-2);
for(ll i=0;i<li;i++)f[i]=f[i]*t%mod;
}
}
}
namespace Ln{
inline void Inv(ll *s,ll *f,ll n){
ll A[N],B[N],S[N];
memset(S,0,sizeof(S));
S[0]=ksm(f[0],mod-2);
for(ll len=2;len<=(n<<1);len<<=1){
ll li=len<<1,l=0;
for(ll i=0;i<len;i++)A[i]=f[i],B[i]=S[i];
for(ll i=len;i<li;i++)A[i]=B[i]=0;
memset(NTT::rev,0,sizeof(NTT::rev));
l=NTT::pre(len,0);
NTT::Ntt(A,1,li);
NTT::Ntt(B,1,li);
for(ll i=0;i<li;i++){
S[i]=(2*B[i]+mod-A[i]*B[i]%mod*B[i]%mod)%mod;
}
NTT::Ntt(S,-1,li);
for(ll i=len;i<li;i++)S[i]=0;
}
for(ll i=0;i<=n;i++)s[i]=S[i];
}
inline void Sqrt(ll *s,ll *f,ll n){
ll A[N],B[N],C[N],S[N];
memset(A,0,sizeof(A));
memset(B,0,sizeof(B));
memset(S,0,sizeof(S));
S[0]=1;
for(ll len=1;len<=(n<<1);len<<=1){
ll li=len<<1,ui;
for(ll i=0;i<li;i++)A[i]=B[i]=C[i]=0;
for(ll i=0;i<len;i++)A[i]=f[i],B[i]=S[i];
Inv(C,B,len);
ui=NTT::pre(len,0);
NTT::Ntt(A,1,li);
NTT::Ntt(C,1,li);
for(ll i=0;i<li;i++)S[i]=A[i]*C[i]%mod;
NTT::Ntt(S,-1,li);
for(ll i=0;i<li;i++)S[i]=(S[i]+B[i])%mod*inv2%mod;
for(ll i=len;i<li;i++)S[i]=0;
}
for(ll i=0;i<=n;i++)s[i]=S[i];
}
}
int main(){
ll n,m;
cin>>n>>m,n--;
for(ll a1,i=0;i<=n;i++){
scanf("%lld",&a1),aa[a1]++;
}
bb[0]=1;
for(ll i=1;i<=m;i++)bb[i]-=4*aa[i];
Ln::Sqrt(bb,bb,m),bb[0]++;
Ln::Inv(ans,bb,m);
for(ll i=1;i<=m;i++)ans[i]=ans[i]*2%mod;
for(ll i=1;i<=m;i++)printf("%lld
",ans[i]);
}