P4389 付公主的背包

· · 闲话

付公主的背包

题目背景

付公主有一个可爱的背包qwq

题目描述

这个背包最多可以装 10^5 大小的东西

付公主有 n 种商品，她要准备出摊了

每种商品体积为 v_i，都有无限件

给定 m，对于 s\in [1,m]，请你回答用这些商品恰好装 s 体积的方案数

输入格式

第一行两个正整数 n,m。 第二行 n 个正整数，表示每种商品的体积。

输出格式

输出 m 行，第 i 行代表 s=i 时方案数，对 998244353 取模。

样例 #1

样例输入 #1

2 4
1 2

样例输出 #1

1
2
2
3

提示

【数据范围】
对于 30\% 的数据，1\le n,m \le 3000；
对于 60\% 的数据，纯随机生成；
对于 100\% 的数据， 1\le n,m \le 10^5，1\le v_i \le m。

简单题，直接写出每个物品的生成函数之后 \ln 然后加起来然后 \exp 回去即可得到答案。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
#define il inline
#define mod 998224353
#define gg 3
#define invg 332748118
#define N 400005
il ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') {f=-1;} c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x*f;
}
ll n,m,v[N],r[N];
ll f[N],lnf[N],expff[N];
il ll qpow(ll a,ll b) {
    ll ans=1;
    while(b) {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
il void NTT(ll *a,ll lim,ll type) {
    for(int i=0;i<lim;i++) if(i<r[i]) swap(a[i],a[r[i]]);
    for(int mid=1;mid<lim;mid<<=1) {
        ll gn=qpow(type==1?gg:invg,(mod-1)/(mid<<1));
        for(int R=mid<<1,j=0;j<lim;j+=R) {
            ll G=1;
            for(int k=0;k<mid;k++,G=(G*gn)%mod) {
                ll x=a[j+k]%mod,y=G*a[j+k+mid]%mod;
                a[j+k]=(x+y)%mod,a[j+k+mid]=(x-y+mod)%mod;
            }
        }
    }
    if(type==-1) {
        ll invlll=qpow(lim,mod-2);
        for(int i=0;i<lim;i++) a[i]=a[i]*invlll%mod;
    }
}
ll c[N],invf[N];
il void getInv(ll len,ll *a,ll *b) {
    if(len==1) {
        b[0]=qpow(a[0],mod-2);
        return;
    }
    getInv((len+1)>>1,a,b);
    ll lim=1,cnt=0;
    while(lim<(len<<1)) {
        lim<<=1;
        cnt++;
    }
    for(int i=0;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(cnt-1));
    for(int i=0;i<len;i++) c[i]=a[i];
    for(int i=len;i<=lim;i++) c[i]=0;
    NTT(c,lim,1),NTT(b,lim,1);
    for(int i=0;i<lim;i++) b[i]=1ll*(2ll-b[i]*c[i]%mod+mod)%mod*b[i]%mod;
    NTT(b,lim,-1);
    for(int i=len;i<lim;i++) b[i]=0;
}
ll da[N];
il void Diff(ll len,ll *a,ll *da) {
    for(int i=0;i<len-1;i++) da[i]=a[i+1]*(i+1)%mod;
    da[len-1]=0;
}
il void Inter(ll len,ll *a,ll *inta) {
    for(int i=len-1;i>=1;i--) {
        inta[i]=a[i-1]*qpow(i,mod-2)%mod;
    }
    inta[0]=0;
}
il void getLn(ll len,ll *a,ll *lna,ll *inva) {
    ll lim=1,cnt=0;
    while(lim<(len<<1)) {
        lim<<=1;
        cnt++;
    } 
    for(int i=0;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(cnt-1));
    for(int i=0;i<lim;i++) inva[i]=c[i]=0;
    getInv(len,a,inva);
    Diff(len,a,da);
    NTT(inva,lim,1);NTT(da,lim,1);
    for(int i=0;i<lim;i++) lna[i]=da[i]*inva[i]%mod;
    NTT(lna,lim,-1);
    Inter(lim,lna,lna);
}
ll a1[N];
il void getExp(ll len,ll *a,ll *expa,ll *lna,ll *inva) {
    if(len==1) {
        expa[0]=1;
        return;
    }
    getExp((len+1)>>1,a,expa,lna,inva);
    getLn(len,expa,lna,inva);
    ll lim=1,cnt=0;
    while(lim<(len<<1)) {
        lim<<=1;
        cnt++;
    }
    for(int i=0;i<len;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(cnt-1));
    for(int i=0;i<len;i++) a1[i]=a[i];
    for(int i=len;i<lim;i++) lna[i]=a1[i]=0;
    for(int i=0;i<lim;i++) a1[i]=((a1[i]-lna[i])%mod+mod)%mod;
    a1[0]=(a1[0]+1)%mod;
    NTT(a1,lim,1);NTT(expa,lim,1);
    for(int i=0;i<lim;i++) expa[i]=expa[i]*a1[i]%mod;
    NTT(expa,lim,-1);
    for(int i=len;i<lim;i++) expa[i]=0;
}
ll sum[N],ans[N];
int main() {
    n=read(),m=read();
    for(int i=1;i<=n;i++) {
        v[i]=read();
        sum[v[i]]++;
    }
    for(int i=1;i<=m;i++) {
        for(int j=1;i*j<=m;j++) {
            f[i*j]=(f[i*j]+(-sum[i]%mod*qpow(j,mod-2)%mod+mod)%mod)%mod;
        }
    }
    getExp(m+1,f,expff,lnf,invf);
    getInv(m+1,expff,ans);
    for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
    return 0;
}

诶，怎么不对啊？