luogu4389 付公主的背包

题目描述：

luogu

题解：

生成函数+多项式exp板子。

首先商品默认无穷件。所以对于价值为$k$的商品，其生成函数为$frac{1}{1-x^k}$。

然后集体取ln求和然后再exp就好了。

但是这个算法的瓶颈在集体取ln。

发现一个性质：$$ln(frac{1}{1-x^k})=-ln(1-x^k)$$

$$=- int frac{-kx^{k-1}}{1-x^k}$$

$$=int kx^{k-1}*sum_{i=0}^{infty}x^{ki}$$

$$=int sum_{i=0}^{infty} kx^{ki+k-1}$$

$$=sum_{i=0}^{infty} frac{x^{k*(i+1)}}{i+1}$$

$$=sum_{i=1}^{infty} frac{x^{ki}}{i}$$

然后？敲板子啊。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 500040;
const int MOD = 998244353;
template<typename T>
inline void read(T&x)
{
    T f = 1,c = 0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}
    x = f*c;
}
template<typename T>
void Mod(T&x){if(x>=MOD)x-=MOD;}
int fastpow(int x,int y)
{
    int ret = 1;
    while(y)
    {
        if(y&1)ret=1ll*ret*x%MOD;
        x=1ll*x*x%MOD;y>>=1;
    }
    return ret;
}
int inv(int x){return fastpow(x,MOD-2);}
int n,m,HS[N],ny[N],to[N],lim,L,LL[N];
int init(int n)
{
    lim = LL[2] = 1;
    while(lim<=n)lim<<=1,LL[lim<<1]=LL[lim]+1;
    return lim;
}
void ntt(int*a,int len,int k)
{
    for(int i=0;i<len;i++)
        if(i<to[i])swap(a[i],a[to[i]]);
    for(int i=1;i<len;i<<=1)
    {
        int w0 = fastpow(3,(MOD-1)/(i<<1));
        for(int j=0;j<len;j+=(i<<1))
        {
            int w = 1;
            for(int o=0;o<i;o++,w=1ll*w*w0%MOD)
            {
                int w1 = a[j+o],w2 = 1ll*a[j+o+i]*w%MOD;
                a[j+o] = (w1+w2)%MOD;
                a[j+o+i] = (w1+MOD-w2)%MOD;
            }
        }
    }
    if(k==-1)
    {
        for(int i=1;i<len>>1;i++)swap(a[i],a[len-i]);
        int Inv = inv(len);
        for(int i=0;i<len;i++)a[i]=1ll*a[i]*Inv%MOD;
    }
}
void get_lim(int len)
{
    lim = len,L = LL[len];
    for(int i=1;i<lim;i++)to[i]=((to[i>>1]>>1)|((i&1)<<(L-1)));
}
int a[N],b[N],c[N];
void mul(int*A,int*B,int len)
{
    get_lim(len<<1);
    for(int i=0;i<lim;i++)a[i]=b[i]=0;
    for(int i=0;i<len;i++)a[i]=A[i],b[i]=B[i];
    ntt(a,lim,1),ntt(b,lim,1);
    for(int i=0;i<lim;i++)c[i]=1ll*a[i]*b[i]%MOD;
    ntt(c,lim,-1);
}
void get_inv(int*F,int*G,int len)
{
    if(len==1){G[0]=inv(F[0]);return ;}
    get_inv(F,G,len>>1);get_lim(len<<1);
    for(int i=0;i<lim;i++)a[i]=b[i]=0;
    for(int i=0;i<len;i++)a[i]=F[i];
    for(int i=0;i<len>>1;i++)b[i]=G[i];
    ntt(a,lim,1),ntt(b,lim,1);
    for(int i=0;i<lim;i++)c[i]=1ll*a[i]*b[i]%MOD*b[i]%MOD;
    ntt(c,lim,-1);
    for(int i=0;i<len;i++)G[i]=(2ll*G[i]%MOD+MOD-c[i])%MOD;
}
void get_d(int*F,int*G,int len)
{
    for(int i=1;i<len;i++)G[i-1]=1ll*F[i]*i%MOD;
    G[len-1] = 0;
}
void get_j(int*F,int*G,int len)
{
    for(int i=len-1;i;i--)G[i]=1ll*F[i-1]*ny[i]%MOD;
    G[0] = 0;
}
int I[N],Ln[N],T[N];
void get_ln(int*F,int*G,int len)
{
    for(int i=0;i<len;i++)I[i]=0;
    get_inv(F,I,len);get_d(F,T,len);mul(T,I,len);
    get_j(c,G,len);
}
void get_exp(int*F,int*G,int len)
{
    if(len==1){G[0]=1;return ;}
    get_exp(F,G,len>>1);get_ln(G,Ln,len);
    for(int i=0;i<len;i++)Mod(Ln[i]=F[i]+MOD-Ln[i]);
    Mod(++Ln[0]);mul(G,Ln,len);
    for(int i=0;i<len;i++)G[i]=c[i];
}
int F[N],G[N];
int main()
{
//    freopen("tt.in","r",stdin);
    read(n),read(m);
    for(int v,i=1;i<=n;i++)
        read(v),HS[v]++;
    int mx = init(m);
    ny[1] = 1;
    for(int i=2;i<mx;i++)
        ny[i] = 1ll*(MOD-MOD/i)*ny[MOD%i]%MOD;
    for(int i=1;i<=m;i++)if(HS[i])
        for(int j=1;i*j<=m;j++)
            Mod(F[i*j]+=1ll*HS[i]*ny[j]%MOD);
    get_exp(F,G,mx);
    for(int i=1;i<=m;i++)
        printf("%d
",G[i]);
    return 0;
}