传送门

神仙题鸭!orz dkw

暴力就是完全背包

而完全背包可以和生成函数扯上关系,记第i种物品质量为\(a_i\),那么这种物品的生成函数\(G(i)=\sum_{j=0}^{\infty}x^{a_ij}\),最后体积为i的答案即为这n个生成函数的卷积的第i项系数

然而用卷积复杂度为\(O(mnlogm)\),还不如暴力.说道卷积,我就想起了可以把多项式先求\(ln\),然后加起来,最后求\(exp\).只不过每个函数求\(ln\)复杂度还是不行,我们打表发现\(lnG(i)=\sum_{j=0}^{\infty}\frac{1}{j}x^{a_ij}\),所以直接把对应项的系数通过枚举倍数加好救星了,复杂度\(O(\sum_{i=1}^{m}\lfloor\frac{m}{i}\rfloor) \approx O(nlogn)\)

#include<bits/stdc++.h>

#define LL long long

#define db double

#define il inline

#define re register

using namespace std;

const int N=270000+10,mod=998244353;

il int rd()

{

    int x=0,w=1;char ch=0;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

il int fpow(int a,int b){int an=1;while(b){if(b&1) an=1ll*an*a%mod;a=1ll*a*a%mod,b>>=1;} return an;}

int rdr[N];

il void ntt(int *a,int n,bool op)

{

	int l=0,x,y;

	while((1<<l)<n) ++l;

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

	for(int i=0;i<n;++i) if(i<rdr[i]) swap(a[i],a[rdr[i]]);

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

	{

		int ww=fpow(op?3:332748118,(mod-1)/(i<<1));

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

			for(int k=0,w=1;k<i;++k,w=1ll*w*ww%mod)

				x=a[j+k],y=1ll*a[j+k+i]*w%mod,a[j+k]=(x+y)%mod,a[j+k+i]=(x-y+mod)%mod;

	}

	if(!op) for(int i=0,w=fpow(n,mod-2);i<n;++i) a[i]=1ll*a[i]*w%mod;

}

int p1[N],p2[N],p3[N],p4[N],p5[N],p6[N],inv[N];

il void polyder(int *a,int *b,int n)

{

	for(int i=0;i<n-1;++i) b[i]=1ll*a[i+1]*(i+1)%mod;

	b[n-1]=b[n]=0;

}

il void polying(int *a,int *b,int n)

{

	for(int i=1;i<n;++i) b[i]=1ll*a[i-1]*inv[i]%mod;

	b[0]=0;

}

il void polyinv(int *a,int *b,int n)

{

	if(n==1){b[0]=fpow(a[0],mod-2);return;}

	polyinv(a,b,n>>1);

	for(int i=0;i<n;++i) p1[i]=a[i],p2[i]=b[i];

	ntt(p1,n<<1,1),ntt(p2,n<<1,1);

	for(int i=0;i<(n<<1);++i) p1[i]=1ll*p1[i]*p2[i]%mod*p2[i]%mod;

	ntt(p1,n<<1,0);

	for(int i=0;i<n;++i) b[i]=((b[i]+b[i])%mod-p1[i]+mod)%mod;

	for(int i=0;i<(n<<1);++i) p1[i]=p2[i]=0;

}

il void polyln(int *a,int *b,int n)

{

	polyder(a,p3,n),polyinv(a,p4,n);

	ntt(p3,n<<1,1),ntt(p4,n<<1,1);

	for(int i=0;i<(n<<1);++i) p3[i]=1ll*p3[i]*p4[i]%mod;

	ntt(p3,n<<1,0);

	polying(p3,b,n);

	for(int i=0;i<(n<<1);++i) p3[i]=p4[i]=0;

}

il void polyexp(int *a,int *b,int n)

{

	if(n==1){b[0]=1;return;}

	polyexp(a,b,n>>1);

	polyln(b,p5,n);

	for(int i=0;i<n;++i) p5[i]=(mod-p5[i]+a[i])%mod,p6[i]=b[i];

	p5[0]=(p5[0]+1)%mod;

	ntt(p5,n<<1,1),ntt(p6,n<<1,1);

	for(int i=0;i<(n<<1);++i) p5[i]=1ll*p5[i]*p6[i]%mod;

	ntt(p5,n<<1,0);

	for(int i=0;i<n;++i) b[i]=p5[i];

	for(int i=0;i<(n<<1);++i) p5[i]=p6[i]=0;

}

int a[N],b[N],cn[N],n,m;

int main()

{

	n=rd(),m=rd();

	inv[0]=inv[1]=1;

	for(int i=2;i<=m;++i) inv[i]=(mod-1ll*mod/i*inv[mod%i]%mod)%mod;

	for(int i=1;i<=n;++i) ++cn[rd()];

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

	{

		if(!cn[i]) continue;

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

			a[i*j]=(a[i*j]+1ll*cn[i]*inv[j]%mod)%mod;

	}

	int l=1;

	while(l<m+1) l<<=1;

	polyexp(a,b,l);

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

    return 0;

}