Description：

有一个背包，每种物品体积为 $v$ ，个数无限，求装满容积为 $[1,m]$ 的背包的方案数。

$1\leqslant n\leqslant 10^5$

Solution：

首先不难想到生成函数： $$ A_i(x)=\sum_{i\geqslant 0}[i|v_i]x^i $$

$$ ans[k]=[x^k]\prod_{i=1}^nA_i(x) $$

首先直接乘复杂度肯定会爆，考虑生成函数的封闭形式： $$ A_i(x)=\frac{1}{1-x^{v_i}} $$ 那么： $$ ans[k]=[x^k]\prod_{i=1}^n\frac1{1-x^{v_i}} $$ 然后据说就是套路了，直接乘不好做，我们可以对他取 $\ln$ 看会发生什么： $$ \ln(\frac1{1-x^{v_k}})=-\ln(1-x^{v_k})=\sum_{i\geqslant 1}\frac1ix^{v_ki} $$ 那么我们可以统计每种体积的物品个数，然后 $O(n\ln n)$ 的求出 $\sum \ln(\frac1{1-x^{v_i}})$ 。

最后再 $\exp$ 回去就行了。

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 cnt[MAXN];

int F[MAXN],G[MAXN];

#define P 998244353

int power(int a,int b)

{

	int res = 1;

	for(;b > 0;b = b >> 1,a = 1ll * a * a % P)if(b & 1)res = 1ll * res * a % P;

	return res;

}

int inver(int a){return power(a,P - 2);}

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

int rev[MAXN];

int init(int n)

{

	int l = 0,len = 1;

	for(;len <= n;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;

	return len;

}

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 invt[MAXN];

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

{

	if(deg == 1)

	{

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

		return;

	}

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

	int l = init(deg * 2);

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

	for(int i = deg;i < l;++i)invt[i] = 0;

	NTT(invt,l,1);NTT(b,l,1);

	for(int i = 0;i < l;++i)b[i] = (2ll * b[i] - 1ll * invt[i] * b[i] % P * b[i] % P + P) % P;

	NTT(b,l,-1);

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

	for(int i = 0;i < l;++i)invt[i] = 0;

	return;

}

int lnt[MAXN];

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

{

	poly_inv(deg,a,lnt);

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

	for(int i = 0;i < deg;++i)b[i] = 1ll * (i + 1) * b[i + 1] % P;

	int l = init(deg * 2);

	NTT(lnt,l,1);NTT(b,l,1);

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

	NTT(b,l,-1);

	for(int i = deg - 1;i >= 1;--i)b[i] = 1ll * inver(i) * b[i - 1] % P;b[0] = 0;

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

	for(int i = 0;i < l;++i)lnt[i] = 0;

	return;

}

int expt[MAXN];

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

{

	if(deg == 1)

	{

		b[0] = 1;

		return;

	}

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

	poly_ln(deg,b,expt);

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

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

	int l = init(deg * 2);

	NTT(expt,l,1);NTT(b,l,1);

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

	NTT(b,l,-1);

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

	for(int i = 0;i < l;++i)expt[i] = 0;

	return;

}

int main()

{

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

	int a;

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

	{

		scanf("%d",&a);

		++cnt[a];

	}

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

		for(int j = 1;j * i <= m;++j)

			F[j * i] = (F[j * i] + 1ll * inver(j) * cnt[i] % P) % P;

	poly_exp(m + 1,F,G);

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

	return 0;

}