P4389

付公主的背包

首先我们知道普通背包是 $O(nm)$ 的。

然后我们想办法生成函数卷积。

对于第 $i$ 个物品，$F_i(x)=1+x^{v_i}+x^{2v_i}+\cdots=\dfrac{1}{1-x^{v_i}}$。

那么答案的多项式显然就是 $G(x)=\prod_{i=1}^{n}F_i(x)$。

直接卷积显然卷出来的复杂度是一堆垃圾。

面对很多个多项式乘积在一起，我们有一个惯用的套路：先 $\ln$ 再 $\exp$。

这个套路很好理解，我们把复杂度多项式乘积换成了更为简单的加法。

那么我们就有：

$$\ln F_i(x)=-\ln(1-x^{v_i})=\sum_{i=1}^{\infty}\dfrac{(x^{v_i})^i}{i}$$

现在不要犯傻，我们多项式相加就是系数相加，根本不需要 $O(n\log n)$ 的多项式 $\ln$。

那么问题来了，多项式相加的复杂度是什么？

显然对于 $\ln F_i(x)$，它的系数只会加在 $v_i$ 的倍数上，那我们需要操作的次数是 $\lfloor \dfrac{m}{v_i}\rfloor$。

这个时候基本都能看出来这个复杂度是个调和级数了。

于是我们可以在 $O(m\log m)$ 的复杂度下求出 $\sum_{i=1}^{n}\ln F_i(x)$。

实际上就是 $\ln(\prod_{i=1}^{n}F_i(x))$。

然后我们再 $O(m\log m)$ 复杂度下 $\exp$ 一下就能得到 $G(x)$ 了。

最后一定要注意，体积相同的物品可以多次出现，一定要把体积相同的物品打包在一起进行系数的累加。

懒了，直接粘全家桶艹过去了。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
#define Clr(f,n) memset(f,0,sizeof(ll)*(n))
#define Cpy(f,g,n) memcpy(f,g,sizeof(ll)*(n))
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writes(ll x) {write(x);putchar(32);}
inline void writeln(ll x) {write(x);putchar(10);}

const ll N=1e6,mo=998244353ll,G=3;

namespace Aeft{
  inline ll Pow(ll b,ll p) {
    ll res=1;while(p) {if(p&1) res=res*b%mo;b=b*b%mo;p>>=1;}return res;
  }
}using Aeft::Pow;

const ll invG=Pow(G,mo-2);

ll n,m;
ll rev[N*2+5],f[N*2+5],inv[N+5],g[N*2+5];

// NTT.
inline void Prev(ll n) {
  for(ll i=0;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)?(n>>1):0);
}
inline void NTT(ll *f,ll n,bool op) {
  Prev(n);for(ll i=0;i<n;i++) if(i<rev[i]) swap(f[i],f[rev[i]]);
  for(ll p=2;p<=n;p<<=1) {
    ll len=p>>1,tG=Pow(op?invG:G,(mo-1)/p);
    for(ll k=0;k<n;k+=p) {
      for(ll l=k,buf=1;l<k+len;l++,buf=buf*tG%mo) {
        ll t=f[l+len]*buf%mo;
        f[l+len]=f[l]-t;if(f[l+len]<0) f[l+len]+=mo;
        f[l]+=t;if(f[l]>mo) f[l]-=mo;
      }
    }
  }
  if(op) {ll invn=Pow(n,mo-2);for(ll i=0;i<n;i++) f[i]=f[i]*invn%mo;}
}
inline void Conv(ll *f,ll *g,ll n) {for(ll i=0;i<n;i++) f[i]=f[i]*g[i]%mo;}
inline void Times(ll *f,ll *g,ll len,ll lim) {
  static ll sav[N*2+5];ll n=1;for(;n<len+len;n<<=1);
  Clr(sav,n);Cpy(sav,g,n);NTT(f,n,0);NTT(sav,n,0);
  Conv(f,sav,n);NTT(f,n,1);Clr(f+lim,n-lim);Clr(sav,n);
}

// Inversion
inline void Invp(ll *f,ll m) {
  ll n;for(n=1;n<m;n<<=1);
  static ll w[N*2+5],r[N*2+5],tmp[N*2+5];
  w[0]=Pow(f[0],mo-2);
  for(ll len=2;len<=n;len<<=1) {
    for(ll i=0;i<(len>>1);i++) r[i]=(w[i]<<1)%mo;
    Cpy(tmp,f,len);NTT(w,len<<1,0);Conv(w,w,len<<1);
    NTT(tmp,len<<1,0);Conv(w,tmp,len<<1);
    NTT(w,len<<1,1);Clr(w+len,len);
    for(ll i=0;i<len;i++) w[i]=(r[i]-w[i]+mo)%mo;
  }
  Cpy(f,w,m);Clr(tmp,n<<1);Clr(w,n<<1);Clr(r,n<<1);
}

// Newton Iteration.
inline void Deriv(ll *f,ll m) {
  for(ll i=1;i<m;i++) {f[i-1]=f[i]*i%mo;}f[m-1]=0;
}
inline void Integr(ll *f,ll m) {
  for(ll i=m;i;i--) {f[i]=f[i-1]*inv[i]%mo;}f[0]=0;
}
inline void Init(ll n) {
  inv[1]=1;for(ll i=2;i<=n;i++) inv[i]=inv[mo%i]*(mo-mo/i)%mo;
}

// Squre root
inline void Sqroot(ll *f,ll m) {
  ll n;for(n=1;n<m;n<<=1);static ll b1[N*2+5],b2[N*2+5];b1[0]=1;
  for(ll len=2;len<=n;len<<=1) {
    for(ll i=0;i<(len>>1);i++) b2[i]=(b1[i]<<1)%mo;
    Invp(b2,len);NTT(b1,len,0);Conv(b1,b1,len);NTT(b1,len,1);
    for(ll i=0;i<len;i++) b1[i]=(f[i]+b1[i])%mo;
    Times(b1,b2,len,len);
  }
  Cpy(f,b1,m);Clr(b1,n+n);Clr(b2,n+n);
}

// Division with Remainder. Here f/g->f f%g->g.
// The quotient is the Prev n-m+1 terms of f.
// The remainder is the Prev m-1 terms of g.
inline void Rev(ll *f,ll n) {
  for(ll i=0;(i<<1)<n-1;i++) swap(f[i],f[n-i-1]);
}
inline void Divid(ll *f,ll *g,ll n,ll m) {
  static ll q[N<<1],t[N<<1];ll l=n-m+1;
  Rev(g,m);Cpy(q,g,l);Rev(g,m);Rev(f,n);Cpy(t,f,l);Rev(f,n);
  Invp(q,l);Times(q,t,l,l);Rev(q,l);Times(g,q,n,n);
  for(ll i=0;i<m-1;i++) {g[i]=(f[i]-g[i]+mo)%mo;}
  Clr(g+m-1,l);Cpy(f,q,l);Clr(f+l,n-l);
}

// Ln & Exp.
inline void Lnp(ll *f,ll m) {
  static ll g[N*2+5];
  Cpy(g,f,m);Invp(g,m);Deriv(f,m);Times(f,g,m,m);
  Integr(f,m-1);Clr(g,m);
}
inline void Exp(ll *f,ll m) {
  static ll s[N*2+5],s2[N*2+5];ll n=1;for(;n<m;n<<=1);s2[0]=1;
  for(ll len=2;len<=n;len<<=1) {
    Cpy(s,s2,len>>1);Lnp(s,len);
    for(ll i=0;i<len;i++) {s[i]=(f[i]-s[i]+mo)%mo;}
    s[0]=(s[0]+1)%mo;Times(s2,s,len,len);
  }
  Cpy(f,s2,m);Clr(s,n);Clr(s2,n);
}

int main() {

  n=read();m=read()+1;Init(m);
  for(ll i=1;i<=n;i++) {
    ll x=read();g[x]++;
  }

  for(ll i=1;i<m;i++) {
    for(ll j=i;j<m;j+=i) f[j]+=inv[j/i]*g[i]%mo;
  }

  Exp(f,m);

  for(ll i=1;i<m;i++) writeln(f[i]);

  return 0;
}