P4389 付公主的背包F公主的背包
如果有标号这题会非常Simple，答案是 \(\sum A^{k}(x)=\dfrac{1}{1-A(x)}\) ，求逆即可。
可惜无标号。。。
所以只能对每种物品分开考虑。
对于一个体积为 \(v\) 的物品，生成函数 \(F(x)=\sum x^{iv}=\dfrac{1}{1-x^v}\) 。
\(G(x)=\prod F(x)\) 即为答案。
都卷起来太不现实。
开始乱试
发现是一堆 \(-1\) 次幂卷起来，那直接 \(\ln\) 就能加了？？？然后 \(\exp\) 回去？
诶这个多项式怎么只有 \(0\) 和 \(1\) 啊，难道可以光速 \(\ln\) ？哦对了，\(\ln\) 了也没法加啊。
所以是整体统计然后最后加了吧。。。
算了，专心考虑怎么 \(\ln\) 。发现不会推，感觉不大对，又没有别的想法。。。
自闭了，看了题解。wtf真就可以光速 \(\ln\) 。
然后回来再试试自己推。
假设我们要求 \(A(x)=\ln (B(x)),B(x)=\dfrac{1}{1-x^v}\)
两边求导
\[A'(x)=\dfrac{B'(x)}{B(x)}\\ =(1-x^v)(\sum vi\ x^{vi-1})\\ =\sum_{i=0} vi\ x^{vi-1}-\sum_{i=1} v(i-1)\ x^{vi-1}\\ =\sum v\ x^{vi-1} \]积分回去
\[A(x)=\sum \dfrac{x^{vi}}{i} \]统计每一种体积的个数 \(cnt_i\) ，直接加就是 \(\sum_{i=1}\dfrac{1}{m}=m\ln m\) 的 了
没想到真就能算，数学太神奇了！或许我刚才肯定一点，硬刚 \(\ln\) 就能自己做出来了呢/kk
最后还有个大常数大码量 \(\exp\) 。。。为了把板子打熟不拉板子>_<，打的真累。。。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mkp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define sz(v) (int)v.size()
typedef long long LL;
typedef double db;
template<class T>bool ckmax(T&x,T y){return x<y?x=y,1:0;}
template<class T>bool ckmin(T&x,T y){return x>y?x=y,1:0;}
#define rep(i,x,y) for(int i=x,i##end=y;i<=i##end;++i)
#define per(i,x,y) for(int i=x,i##end=y;i>=i##end;--i)
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f?x:-x;
}
#define mod 998244353
const int N=100005;
const int M=N<<2;
namespace math{
int inv[N];
inline int qpow(int n,int k){int res=1;for(;k;k>>=1,n=1ll*n*n%mod)if(k&1)res=1ll*n*res%mod;return res;}
inline void fmod(int&x){x-=mod,x+=x>>31&mod;}
void initmath(const int n=N-5){
inv[1]=1;for(int i=2;i<=n;++i)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
}
}
using math::qpow;
using math::fmod;
namespace poly{
int rev[M],lg,lim;
void init_poly(const int&n){
for(lim=1,lg=0;lim<n;lim<<=1,++lg);
for(int i=0;i<lim;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));
}
void NTT(int*a,int op){
for(int i=0;i<lim;++i)
if(i>rev[i])swap(a[i],a[rev[i]]);
const int g=op?3:math::inv[3];
for(int i=1;i<lim;i<<=1){
const int wn=qpow(g,(mod-1)/(i<<1));
for(int j=0;j<lim;j+=i<<1){
int w0=1;
for(int k=0;k<i;++k,w0=1ll*w0*wn%mod){
const int X=a[j+k],Y=1ll*w0*a[i+j+k]%mod;
fmod(a[j+k]=X+Y),fmod(a[i+j+k]=X-Y+mod);
}
}
}
if(op)return;int ilim=qpow(lim,mod-2);
for(int i=0;i<lim;++i)a[i]=1ll*a[i]*ilim%mod;
}
#define clr(a,n) memset(a,0,sizeof(int)*(n))
#define cpy(a,b,n) memcpy(a,b,sizeof(int)*(n))
void poly_mul(int*f,int*g,int*ans,int n,int m){
static int A[M],B[M];init_poly(n+m);
cpy(A,f,n),clr(A+n,lim-n),NTT(A,1);
cpy(B,g,m),clr(B+m,lim-m),NTT(B,1);
for(int i=0;i<lim;++i)ans[i]=1ll*A[i]*B[i]%mod;
NTT(ans,0);
}
void poly_inv(int*g,int*f,int n){
static int A[M];
if(n==1)return g[0]=qpow(f[0],mod-2),void();
poly_inv(g,f,(n+1)>>1);
init_poly(n<<1);
cpy(A,f,n),clr(A+n,lim-n),clr(g+n,lim-n);
NTT(A,1),NTT(g,1);
for(int i=0;i<lim;++i)g[i]=1ll*g[i]*(2-1ll*A[i]*g[i]%mod+mod)%mod;
NTT(g,0),clr(g+n,lim-n);
}
void dao(int*g,int*f,int n){
for(int i=0;i<n-1;++i)g[i]=1ll*(i+1)*f[i+1]%mod;g[n-1]=0;
}
void jif(int*g,int*f,int n){
for(int i=1;i<=n;++i)g[i]=1ll*f[i-1]*math::inv[i]%mod;g[0]=0;
}
void poly_ln(int*g,int*f,int n){
static int A[M],B[M];
dao(A,f,n),clr(B,n),poly_inv(B,f,n),poly_mul(A,B,A,n,n),jif(g,A,n);
}
void poly_exp(int*g,int*f,int n){
static int A[M];
if(n==1)return g[0]=1,void();
poly_exp(g,f,(n+1)>>1);
clr(A,n),poly_ln(A,g,n);
for(int i=0;i<n;++i)fmod(A[i]=(!i)+mod+f[i]-A[i]);
poly_mul(g,A,g,n,n),clr(g+n,lim-n);
}
}
int n,m,cnt[N],f[N],g[M];
signed main(){
math::initmath(),n=read(),m=read()+1;
for(int i=1;i<=n;++i)++cnt[read()];
for(int i=1;i<m;++i){
if(!cnt[i])continue;
for(int j=1;i*j<m;++j)fmod(f[i*j]+=1ll*cnt[i]*math::inv[j]%mod);
}
poly::poly_exp(g,f,m);
for(int i=1;i<m;++i)printf("%d\n",g[i]);
return 0;
}