Description：

一棵树的所有点的点权都是给定的集合 $S$ 中的一个数。 求出 $1$ 到 $m$ 中节点个数为 $n$ 权值和为 $k$ 的树的个数。

$1\leqslant n\leqslant 10^5$

Solution：

考虑生成函数， $F(x)$ 表示答案的生成函数， $\begin{align}C(x)=\sum_{i=1}^\infty[i\text{ in }S]x^i\end{align}$ ，那么可以发现： $$ F(x)=F^2(x)C(x)+1 $$ 解这个方程，得： $$ F=\frac{1\pm \sqrt{1-4C}}{2C} $$ 这个不太好看出来应该取 $+$ 还是 $-$ ，但是我们换一种方式： $$ F=\frac{2}{1\pm\sqrt{1-4C}} $$ 显然当取 $+$ 时 $F(0)=1$ ，所以多项式开方 $+$ 多项式求逆即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 400010

int ww[MAXN << 1],*g = ww + MAXN;

int rev[MAXN];

#define P 998244353

int power(int a,int b)

{

	int res = 1;

	while(b > 0)

	{

		if(b & 1)res = 1ll * res * a % P;

		a = 1ll * a * a % P;

		b = b >> 1;

	}

	return res;

}

void NTT(int f[],int l,int type)

{

	for(int i = 0;i < l;++i)

	{

		if(i < rev[i])swap(f[i],f[rev[i]]);

	}

	for(int i = 2;i <= l;i = i << 1)

	{

		int wn = g[type * l / i];

		for(int j = 0;j < l;j += i)

		{

			int w = 1;

			for(int k = j;k < j + i / 2;++k)

			{

				int u = f[k],t = 1ll * w * f[k + i / 2] % P;

				f[k] = (u + t) % P;

				f[k + i / 2] = (u - t + P) % P;

				w = 1ll * w * wn % P;

			}

		}

	}

	if(type == -1)

	{

		int ni = power(l,P - 2);

		for(int i = 0;i < l;++i)f[i] = 1ll * f[i] * ni % P;

	}

	return;

}

int invtmp[MAXN];

void calc_inv(int deg,int a[],int b[])

{

	if(deg == 1)

	{

		b[0] = power(a[0],P - 2);

		return;

	}

	calc_inv((deg + 1) >> 1,a,b);

	int l = 0,len = 1;

	for(;len <= (deg << 1);len = len << 1)++l;

	for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	g[0] = g[-len] = 1;g[1] = g[1 - len] = power(3,(P - 1) / len);

	for(int i = 2;i < len;++i)g[i] = g[i - len] = 1ll * g[i - 1] * g[1] % P;

	for(int i = 0;i < deg;++i)invtmp[i] = a[i];

	for(int i = deg;i < len;++i)invtmp[i] = 0;

	NTT(invtmp,len,1);NTT(b,len,1);

	for(int i = 0;i < len;++i)

	{

		b[i] = (2 * b[i] % P - 1ll * invtmp[i] * b[i] % P * b[i] % P + P) % P;

	}

	NTT(b,len,-1);

	for(int i = deg;i < len;++i)b[i] = 0;

	//for(int i = 0;i < deg;++i)cout << b[i] * 2 % P << " ";cout << endl;

	return;

}

int multmp[MAXN];

void mul(int deg,int a[],int b[])

{

	int l = 0,len = 1;

	for(;len <= (deg << 1);len = len << 1)++l;

	for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	g[0] = g[-len] = 1;g[1] = g[1 - len] = power(3,(P - 1) / len);

	for(int i = 2;i < len;++i)g[i] = g[i - len] = 1ll * g[i - 1] * g[1] % P;

	for(int i = 0;i < len;++i)multmp[i] = b[i];

	NTT(a,len,1);NTT(multmp,len,1);

	for(int i = 0;i < len;++i)

	{

		a[i] = 1ll * a[i] * multmp[i] % P;

	}

	NTT(a,len,-1);

	for(int i = deg;i < len;++i)a[i] = 0;

	return;

}

#define REM 1

int tmp1[MAXN],tmp2[MAXN];

void calc_sqr(int deg,int a[],int b[])

{

	if(deg == 1)

	{

		b[0] = REM;

		return;

	}

	calc_sqr((deg + 1) >> 1,a,b);

	for(int i = 0;i < deg;++i)tmp1[i] = b[i];

	mul(deg,tmp1,b);

	for(int i = 0;i < deg;++i)tmp1[i] = (tmp1[i] - a[i] + P) % P;

	memset(tmp2,0,sizeof(tmp2));

	calc_inv(deg,b,tmp2);

	for(int i = 0;i < deg;++i)tmp2[i] = 1ll * tmp2[i] * power(2,P - 2) % P;

	mul(deg,tmp1,tmp2);

	for(int i = 0;i < deg;++i)b[i] = (b[i] - tmp1[i] + P) % P;

	return;

}

int H[MAXN],F[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	int x;

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&x);

		H[x] = 1;

	}

	++m;

	for(int i = 0;i < m;++i)H[i] = (-4ll * H[i] % P + P) % P;

	H[0] = (H[0] + 1) % P;

	calc_sqr(m,H,F);

	F[0] = (F[0] + 1) % P;

	memset(H,0,sizeof(H));

	calc_inv(m,F,H);

	for(int i = 0;i < m;++i)H[i] = 2 * H[i] % P;

	for(int i = 1;i < m;++i)printf("%d\n",H[i]);

	return 0;

}