题面
题解
设多项式的第a项为权值和为a的二叉树个数，多项式的第a项表示是否为真，即
则，所以F是三个多项式的卷积，其中包括自己：
，1是F的常数项，即。
我们发现这是一个一元二次方程，可以求出，因为g的常数项为零，所以1-4g的常数项为1，的常数项也为1，的常数项就为零，就跑不了逆元，所以舍掉。
最终，跑一个多项式开根和一个多项式求逆就行。
CODE
大常数TLE的代码， 自己优化吧（逃
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define LL long long
#define MAXN 800005
//#define int LL
#define LENTH (LERTH*sizeof(int))
#pragma GCC optimize(2)
#pragma G++ optimize(3)
inline int read() {
int f = 1,x = 0;char s = getchar();
while(s < '0' || s > '9') {if(s == '-') f = -1;s = getchar();}
while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();}
return x * f;
}
int fan[MAXN],mod = 998244353,n,m,q,i,j,s,o,k,t,a[MAXN],b[MAXN],f[MAXN],g[MAXN],LERTH;
inline int readm() {
int f = 1,x = 0;char s = getchar();
while(s < '0' || s > '9') {if(s == '-') f = -1;s = getchar();}
while(s >= '0' && s <= '9') {x = (x * 10ll % mod + s - '0') % mod;s = getchar();}
return x * f;
}
inline int qkpow(int a,int b) {
int res = 1;
while(b>0) {
if(b&1) res = 1ll*res*a%mod;
a = 1ll*a*a%mod;
b>>=1;
}
return res;
}
int INV[MAXN];
int mod2 = 998244353;
inline void NTT(int len,int *a,int temp) {
int ugly = (int)round(log2(len));
for(int i = 1;i < len;i ++) {
fan[i] = (fan[i>>1]>>1)|((i&1)<<(ugly-1));
if(i<fan[i])
swap(a[i],a[fan[i]]);
}
for(int k = 2;k <= len;k <<= 1) {
int t = k / 2;
int vw = (temp == 1)? qkpow(3,(mod -1) / k):qkpow(3,(mod-1) - (mod-1)/k);
for(int i = 0;i < len;i += k) {
int w2 = 1;
for(int j = 0;j < t;j ++,w2 = 1ll*w2*vw % mod) {
int w3 = a[i + j],w4 = a[i + j + t];
a[i + j] = (0ll+w3 + w4*1ll*w2) % mod;
a[i + j + t] = ((0ll+w3 - w2*1ll*w4)%mod + mod) % mod;
}
}
}
if(temp == 1) return ;
int invmod = qkpow(len,mod - 2);
for(int i = 0;i < len;i ++) {
a[i] = 1ll*a[i] * invmod % mod;
}
return ;
}
inline void DXSC(int *A,int *B,int *C,int la,int lb,int &lc) {
int le = 1,nm = la + lb;
while(le <= nm) le <<= 1;
NTT(le,A,1);
NTT(le,B,1);
for(int i = 0;i <= le;i ++) C[i] = 1ll*A[i]*B[i] % mod;
NTT(le,C,-1);
lc = nm;
return ;
}
inline void work(int n) {
int le = 1;while(le <= 2*n) le <<= 1;
for(int i = 0;i < le;i ++) f[i] = g[i] = 0;
for(int i = 0;i < n;i ++) f[i] = a[i];
for(int i = 0;i < n;i ++) g[i] = b[i];
NTT(le,f,1);NTT(le,g,1);
for(int i = 0;i < le;i ++) f[i] = g[i] * 2ll - 1ll*g[i]*g[i] % mod * f[i] % mod,f[i]%= mod;
NTT(le,f,-1);
for(int i = 0;i < n;i ++) b[i] = (f[i]%mod + mod) % mod;
}
inline void inv(int *A,int *B,int n) {
memset(a,0,LENTH);
memset(b,0,LENTH);
memset(B,0,LENTH);
for(int i = 0;i < n;i ++) a[i] = A[i];
b[0] = qkpow(a[0],mod - 2);
int m = 1;
while(m < n) {
m <<= 1;
work(m);
}
for(int i = 0;i < n;i ++) B[i] = b[i];
return ;
}
inline void deriv(int *A,int *B,int len) {
for(int i = 0;i < len;i ++) B[i] = (1ll + i) * A[i + 1] % mod;B[len] = 0;
}
inline void integ(int *A,int *B,int len) {
for(int i = len + 1;i > 0;i --) B[i] = 1ll * INV[i] * A[i - 1] % mod;B[0] = 0;
}
inline void putd(int *a,int len) {
for(int i = 0;i <= len;i ++) printf("%d ",a[i]);putchar('\n');
}
int ai[MAXN],bi[MAXN],c[MAXN],d[MAXN],h[MAXN];
inline void polyln(int *A,int *B,int n) {
int m = n + 1;
memset(ai,0,LENTH);
memset(bi,0,LENTH);
memset(c,0,LENTH);
memset(d,0,LENTH);
memset(h,0,LENTH);
for(int i = 0;i <= n;i ++) ai[i] = A[i];
deriv(ai,c,n);
inv(ai,d,m);
DXSC(c,d,h,n-1,n,k);
integ(h,bi,n-1);
memset(B,0,LENTH);
for(int i = 0;i <= n;i ++) {
B[i] = bi[i];
}
}
int cc[MAXN],ee[MAXN],dd[MAXN],inv2 = qkpow(2ll,mod - 2) % mod;
inline void polyexp(int *A,int *B,int n) {
int m = 1;
memset(B,0,LENTH);
B[0] = 1;
while(m < n+1) {
m<<= 1;
memcpy(cc,B,LENTH);
memcpy(ee,B,LENTH);
polyln(cc,cc,m-1);
for(int i = 0;i < m;i ++) cc[i] = (0ll+A[i] + mod - cc[i]) % mod;cc[0] = (cc[0] + 1ll) % mod;
DXSC(ee,cc,ee,m-1,m-1,k);
for(int i = 0;i < m;i ++) B[i] = (ee[i]%mod + mod) % mod;
}
for(int i = n+1;i <= m;i ++) B[i] = 0;
return ;
}
void polysqrt(int *A,int *B,int n) {
int m = 1;
memset(B,0,LENTH);
B[0] = 1;
while(m < n+1) {
m <<= 1;
memcpy(ee,B,LENTH);
memset(dd,0,LENTH);
for(int i = 0;i < m;i ++) dd[i] = A[i];
inv(B,cc,m);
int le = 1;while(le <= m*2) le<<=1;
NTT(le,cc,1);NTT(le,dd,1);NTT(le,ee,1);
for(int i = 0;i <= le;i ++) ee[i] = 1ll*inv2*(0ll + ee[i] + 1ll*dd[i] * cc[i] % mod) % mod;
NTT(le,ee,-1);
for(int i = 0;i < m;i ++) B[i] = (ee[i]%mod + mod) % mod;
}
for(int i = n+1;i <= m;i ++) B[i] = 0;
return ;
}
int FF[MAXN],deltag[MAXN],sqrtg[MAXN],doubleg[MAXN];
int main() {
n = read();m = read();
for(LERTH=1;LERTH <= m;LERTH<<=1);
for(int i = 1;i <= n;i ++) {
s = read();
if(s <= m) deltag[s] = mod - 4;
}deltag[0] = 1;
polysqrt(deltag,sqrtg,m);
sqrtg[0] = (sqrtg[0] + mod + 1ll) % mod;
inv(sqrtg,FF,m + 1);
for(int i = 1;i <= m;i ++) {
printf("%d\n",(FF[i]*2ll) % mod);
}
return 0;
}
