「Luogu P4389」付公主的背包

发表于 |
字数统计: 1.3k | 阅读时长 ≈ 7

给定$n$种物品，每种物品的体积为$w_i$，有无限个。对于$c\in[1,m]$，求出用这些物品正好装满体积为$c$的背包的总数。

$\texttt{Data Range:}n,m\leq 10^5,w_i\leq m$

链接

Luogu P4389

题解

考虑写出每种物品的生成函数。

如果没有体积的限制，那生成函数是

但是有了体积的限制，咋办？

考虑将一个体积为$v$的物品拆成$v$个体积为$1$的物品，再把这些体积为$1$的物品每$v$个捆绑成一组。所以说，你每次只能拿$v$的倍数个体积为$1$的物品，那么生成函数就是

也即

写成封闭形式，有

于是答案就是每种物品对应的生成函数的卷积。可是时间复杂度过高，考虑优化。

假设第$i$种物品所对应的生成函数为$F_i(x)$，答案所对应的生成函数为$G(x)$，则

于是很自然的想到两边取对数，有

暴力的求$\ln F_i(x)$是$O(n^2\log n)$的，所以考虑巧妙的求，所以开始推柿子。

设$H(x)=\ln F(x)$，则

展开得

暴力乘上去

所以说

对每种物品求出该多项式相加后$\texttt{exp}$即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=4e5+51,MOD=998244353,G=3,INVG=332748118;
ll cnt,fd;
ll f[MAXN],tmp[MAXN],res[MAXN],rev[MAXN],fact[MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline ll qpow(ll base,ll exponent)
{
    li res=1;
    while(exponent)
    {
        if(exponent&1)
        {
            res=(li)res*base%MOD;
        }
        base=(li)base*base%MOD,exponent>>=1;
    }
    return res;
}
inline void setup(ll ccnt)
{
    fact[0]=fact[1]=1;
    for(register int i=2;i<=ccnt;i++)
    {
        fact[i]=(li)fact[i-1]*i%MOD;
    }
}
inline void NTT(ll *cp,ll cnt,ll inv)
{
    ll cur=0,res=0,omg=0;
    for(register int i=0;i<cnt;i++)
    {
        if(i<rev[i])
        {
            swap(cp[i],cp[rev[i]]);
        }
    }
    for(register int i=2;i<=cnt;i<<=1)
    {
        cur=i>>1,res=qpow(inv==1?G:INVG,(MOD-1)/i);
        for(register ll *p=cp;p!=cp+cnt;p+=i)
        {
            omg=1;
            for(register int j=0;j<cur;j++)
            {
                ll t=(li)omg*p[j+cur]%MOD,t2=p[j];
                p[j+cur]=(t2-t+MOD)%MOD,p[j]=(t2+t)%MOD;
                omg=(li)omg*res%MOD;
            }
        }
    }
    if(inv==-1)
    {
        ll invl=qpow(cnt,MOD-2);
        for(register int i=0;i<=cnt;i++)
        {
            cp[i]=(li)cp[i]*invl%MOD;
        }
    }
}
inline void deriv(ll fd,ll *f,ll *res)
{
    for(register int i=1;i<fd;i++)
    {
        res[i-1]=(li)f[i]*i%MOD;
    }
    res[fd-1]=0;
}
inline void integ(ll fd,ll *f,ll *res)
{
    for(register int i=1;i<fd;i++)
    {
        res[i]=(li)f[i-1]*qpow(i,MOD-2)%MOD;
    }
    res[0]=0;
}
inline void inv(ll fd,ll *f,ll *res)
{
    static ll tmp[MAXN];
    if(fd==1)
    {
        res[0]=qpow(f[0],MOD-2);
        return;
    }
    inv((fd+1)>>1,f,res);
    ll cnt=1,limit=-1;
    while(cnt<(fd<<1))
    {
        cnt<<=1,limit++;
    }
    for(register int i=0;i<cnt;i++)
    {
        tmp[i]=i<fd?f[i]:0;
        rev[i]=(rev[i>>1]>>1)|((i&1)<<limit);
    }
    NTT(tmp,cnt,1),NTT(res,cnt,1);
    for(register int i=0;i<cnt;i++)
    {
        res[i]=(li)(2-(li)tmp[i]*res[i]%MOD+MOD)%MOD*res[i]%MOD;
    }
    NTT(res,cnt,-1);
    for(register int i=fd;i<cnt;i++)
    {
        res[i]=0;
    }
}
inline void ln(ll fd,ll *f,ll *res)
{
    static ll pinv[MAXN],der[MAXN];
    ll cnt=1,limit=-1;
    while(cnt<(fd<<1))
    {
        cnt<<=1,limit++;
    }
    inv(fd,f,pinv),deriv(fd,f,der);
    for(register int i=0;i<cnt;i++)
    {
        rev[i]=(rev[i>>1]>>1)|((i&1)<<limit);
    }
    NTT(pinv,cnt,1),NTT(der,cnt,1);
    for(register int i=0;i<cnt;i++)
    {
        der[i]=(li)der[i]*pinv[i]%MOD;
    }
    NTT(der,cnt,-1),integ(fd,der,res);
    for(register int i=0;i<cnt;i++)
    {
        der[i]=pinv[i]=0;
    }
}
inline void exp(ll fd,ll *f,ll *res)
{
    static ll texp[MAXN];
    if(fd==1)
    {
        res[0]=1;
        return;
    }
    ll cnt=1,limit=-1;
    while(cnt<(fd<<1))
    {
        cnt<<=1,limit++;
    }
    exp((fd+1)>>1,f,res),ln(fd,res,texp);
    for(register int i=0;i<cnt;i++)
    {
        rev[i]=(rev[i>>1]>>1)|((i&1)<<limit);
    }
    texp[0]=(f[0]+1-texp[0]+MOD)%MOD;
    for(register int i=1;i<fd;i++)
    {
        texp[i]=(f[i]-texp[i]+MOD)%MOD;
    }
    NTT(texp,cnt,1),NTT(res,cnt,1);
    for(register int i=0;i<cnt;i++)
    {
        res[i]=(li)res[i]*texp[i]%MOD;
    }
    NTT(res,cnt,-1);
    for(register int i=0;i<cnt;i++)
    {
        texp[i]=0,res[i]=i<fd?res[i]:0;
    }
}
int main()
{
    cnt=read(),fd=read();
    for(register int i=0;i<cnt;i++)
    {
    	tmp[read()]++; 
    }
    for(register int i=1;i<=fd;i++)
    {
        if(tmp[i])
        {
            for(register int j=i;j<=fd;j+=i)
            {
                f[j]=(f[j]+(li)tmp[i]*i%MOD*qpow(j,MOD-2)%MOD)%MOD; 
            }
        }
    }
    exp(fd+1,f,res);
    for(register int i=1;i<=fd;i++)
    {
        printf("%d\n",res[i]);
    }
}