Luogu

分析

考虑写出所有物品的生成函数
$$
F(x)=\sum_{i=0}^\infty[i\bmod V=0]x^i=\frac{1}{1-x^V}
$$
显然答案就是所有物品的生成函数的卷积，然而这样子时间复杂度过高，考虑优化。

考虑把所有生成函数求 ln 后加起来，再 exp 回去。

设 $G(x)=\ln(F(x))$ ，那么有
$$
\begin{aligned}
G'(x)=&\frac{F'(x)}{F(x)}\\
=&(1-x^V)F'(x)\\
=&(1-x^V)\sum_{i=1}^\infty Vix^{Vi-1}\\
=&\sum_{i=1}^\infty Vx^{Vi-1}
\end{aligned}
$$
于是有
$$
\begin{aligned}
G(x)=&\int G'(x)\mathrm{d}x\\
=&\sum_{i=1}^\infty\frac{1}{i}x^{Vi}
\end{aligned}
$$
于是可以调和级数的处理出 $G(x)$，然后多项式 exp 即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400000+10;
const int mod=998244353,G=3,Gi=(mod+1)/G;

inline int qpow(int a,int b) {
    int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod)
        if (b&1) c=1ll*c*a%mod;
    return c;
}

int r[N];

inline void NTT(int* A,int n,int op) {
    for (re int i=0;i<n;++i) if (i<r[i]) swap(A[i],A[r[i]]);
    for (re int i=1;i<n;i<<=1) {
        int rot=qpow(op==1?G:Gi,(mod-1)/(i<<1));
        for (re int j=0;j<n;j+=(i<<1)) {
            int w=1;
            for (re int k=0;k<i;++k,w=1ll*w*rot%mod) {
                int x=A[j+k],y=1ll*w*A[j+k+i]%mod;
                A[j+k]=(x+y)%mod,A[j+k+i]=(x-y+mod)%mod;
            }
        }
    }
    if (op==-1) {
        int inv=qpow(n,mod-2);
        for (re int i=0;i<n;++i) A[i]=1ll*A[i]*inv%mod;
    }
}

inline void getinv(int* f,int* g,int n) {
    static int A[N],B[N];
    if (n==1) { g[0]=qpow(f[0],mod-2); return; }
    getinv(f,g,n>>1);
    for (re int i=0;i<n;++i) A[i]=f[i],B[i]=g[i];
    int lim=1,l=0;
    for (;lim<=n;lim<<=1,++l);
    for (re int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    NTT(A,lim,1),NTT(B,lim,1);
    for (re int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod*B[i]%mod;
    NTT(A,lim,-1);
    for (re int i=0;i<n;++i) g[i]=(g[i]+g[i])%mod;
    for (re int i=0;i<n;++i) g[i]=(g[i]+mod-A[i])%mod;
    for (re int i=0;i<lim;++i) A[i]=B[i]=0;
}

inline void getderi(int* f,int* g,int n) {
    for (re int i=1;i<n;++i) g[i-1]=1ll*i*f[i]%mod;
    g[n]=g[n-1]=0;
}

inline void getinte(int* f,int* g,int n) {
    for (re int i=1;i<n;++i) g[i]=1ll*f[i-1]*qpow(i,mod-2)%mod;
    g[0]=0;
}

inline void getln(int* f,int* g,int n) {
    static int A[N],B[N];
    getderi(f,A,n),getinv(f,B,n);
    int lim=1,l=0;
    for (;lim<=n;lim<<=1,++l);
    for (re int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    NTT(A,lim,1),NTT(B,lim,1);
    for (re int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod;
    NTT(A,lim,-1); getinte(A,g,n);
    for (re int i=0;i<lim;++i) A[i]=B[i]=0;
}

inline void getexp(int* f,int* g,int n) {
    static int A[N],B[N];
    if (n==1) { g[0]=1; return; }
    getexp(f,g,n>>1);
    for (re int i=0;i<n;++i) A[i]=g[i];
    getln(g,B,n);
    for (re int i=0;i<n;++i) B[i]=(mod-B[i]+f[i])%mod;
    B[0]=(B[0]+1)%mod;
    int lim=1,l=0;
    for (;lim<=n;lim<<=1,++l);
    for (re int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    NTT(A,lim,1),NTT(B,lim,1);
    for (re int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod;
    NTT(A,lim,-1);
    for (re int i=0;i<n;++i) g[i]=A[i];
    for (re int i=0;i<lim;++i) A[i]=B[i]=0;
}

int n,m,a[N];
int f[N],g[N];

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) ++a[read()];
    int lim=1; for (;lim<=m;lim<<=1);
    for (re int i=1;i<=m;++i) {
        if (!a[i]) continue;
        for (re int j=i;j<=m;j+=i)
            f[j]=(f[j]+1ll*a[i]*i%mod*qpow(j,mod-2))%mod;
    }
    getexp(f,g,lim);
    for (re int i=1;i<=m;++i) printf("%d\n",g[i]);
    return 0;
}