P4389 付公主的背包
题目背景
付公主有一个可爱的背包qwq
题目描述
这个背包最多可以装(10^5)大小的东西
付公主有(n)种商品，她要准备出摊了
每种商品体积为(V_i)，都有(10^5)件
给定(m)，对于(sin [1,m])，请你回答用这些商品恰好装(s)体积的方案数
输入输出格式
输入格式：
第一行(n,m)
第二行(V_1sim V_n)
输出格式：
(m)行，第(i)行代表(s=i)时方案数，对(998244353)取模
说明
对于(30\%)的数据，(nle 3000,mle 3000)
对于(60\%)的数据，纯随机生成
对于(100\%)的数据， (nle 100000,mle 100000)
对于(100\%)的数据，(V_ile m)
先构造一波生成函数
[F_k(x)=sum_{i=0}^{infty}x^{iv_k}=frac{1}{1-x^{v_k}}
]
然后答案是(n)个东西卷起来，复杂度高达(O(nmlog m))，显然苟不住
不妨把(n)个函数都取对数，然后就成了多项式加法，可以直接枚举倍数做到(O(mln m))，现在考虑如何转换成为对数
[egin{aligned}
G&=ln F\
G'&=frac{F'}{F}\
&=(1-x^v)sum_{i=0}^infty vix^{vi-1}\
&=sum_{i=0}^infty vix^{vi-1}-sum_{i=0}^infty vix^{v(i+1)-1}\
&=sum_{i=0}^infty vix^{vi-1}-sum_{i=0}^infty v(i-1)x^{vi-1}\
&=sum_{i=0}^infty vix^{vi-1}\
G&=int G'\
&=sum_{i=0}^infty frac{1}{i}x^{vi}
end{aligned}
]
于是我们需要实现的就只有多项式exp啦
Code:
#include <cstdio>
#include <algorithm>
const int N=(1<<18)+10;
const int mod=998244353,Gi=332748118;
#define mul(a,b) (1ll*(a)*(b)%mod)
#define add(a,b) ((a+b)%mod)
int ans[N],G[N],turn[N],ina[N],inb[N],lna[N],lnb[N],exa[N],exb[N],cnt[N],Inv[N];
int qp(int d,int k){int f=1;while(k){if(k&1)f=mul(f,d);d=mul(d,d),k>>=1;}return f;}
void NTT(int *a,int typ,int len)
{
int L=-1;for(int i=1;i<len;i<<=1) ++L;
for(int i=0;i<len;i++)
{
turn[i]=turn[i>>1]>>1|(i&1)<<L;
if(i<turn[i]) std::swap(a[i],a[turn[i]]);
}
for(int le=1;le<len;le<<=1)
{
int wn=qp(typ?3:Gi,(mod-1)/(le<<1));
for(int p=0;p<len;p+=le<<1)
{
int w=1;
for(int i=p;i<p+le;i++,w=mul(w,wn))
{
int tx=a[i],ty=mul(w,a[i+le]);
a[i]=add(tx,ty);
a[i+le]=add(tx,mod-ty);
}
}
}
if(!typ)
{
int inv=qp(len,mod-2);
for(int i=0;i<len;i++) a[i]=mul(a[i],inv);
}
}
void polyinv(int *a,int *b,int len)
{
if(len==1){b[0]=qp(a[0],mod-2);return;}
polyinv(a,b,len>>1);
for(int i=0;i<len<<1;i++) ina[i]=inb[i]=0;
for(int i=0;i<len;i++) ina[i]=b[i],inb[i]=a[i];
NTT(ina,1,len<<1),NTT(inb,1,len<<1);
for(int i=0;i<len<<1;i++) ina[i]=mul(ina[i],add(2,mod-mul(ina[i],inb[i])));
NTT(ina,0,len<<1);
for(int i=0;i<len;i++) b[i]=ina[i];
}
void inter(int *a,int n){for(int i=n;i;i--)a[i]=mul(a[i-1],Inv[i]);a[0]=0;}
void drev(int *a,int n){for(int i=0;i<n;i++)a[i]=mul(a[i+1],i+1);a[n]=0;}
void polyln(int *a,int *b,int len)
{
for(int i=0;i<len<<1;i++) lna[i]=lnb[i]=0;
for(int i=0;i<len;i++) lna[i]=a[i];
polyinv(lna,lnb,len);
drev(lna,len-1);
NTT(lna,1,len<<1),NTT(lnb,1,len<<1);
for(int i=0;i<len<<1;i++) lna[i]=mul(lna[i],lnb[i]);
NTT(lna,0,len<<1);
inter(lna,len-1);
for(int i=0;i<len;i++) b[i]=lna[i];
}
void polyexp(int *a,int *b,int len)
{
if(len==1){b[0]=1;return;}
polyexp(a,b,len>>1);
for(int i=0;i<len<<1;i++) exa[i]=exb[i]=0;
polyln(b,exa,len);
for(int i=0;i<len;i++) exa[i]=add(a[i]+(i==0),mod-exa[i]);
for(int i=0;i<len;i++) exb[i]=b[i];
NTT(exa,1,len<<1),NTT(exb,1,len<<1);
for(int i=0;i<len<<1;i++) exa[i]=mul(exa[i],exb[i]);
NTT(exa,0,len<<1);
for(int i=0;i<len;i++) b[i]=exa[i];
}
int main()
{
int n,m;scanf("%d%d",&n,&m);
for(int v,i=1;i<=n;i++) scanf("%d",&v),++cnt[v];
++m;int len=1;while(len<m) len<<=1;
Inv[0]=1;for(int i=1;i<=len;i++) Inv[i]=qp(i,mod-2);
for(int i=1;i<=m;i++)
for(int j=i;j<=m;j+=i)
G[j]=add(G[j],mul(cnt[i],Inv[j/i]));
polyexp(G,ans,len);
for(int i=1;i<m;i++) printf("%d
",ans[i]);
return 0;
}
2018.12.29