P4389 付公主的背包 生成函数+多项式ln+多项式exp

传送门：https://www.luogu.com.cn/problem/P4389

题意

有n个物品，每个物品体积为$v_i$，给定一个m，问这些物品恰好装[1,m]的方案数。

思路

如果数据量小，则可以背包。 但问题是，n和m都有1e5，不可能背包的。

因为是一类计数问题，所以考虑生成函数。

设只装一个物品体积v，它可以用多大的背包，那就是v，2v，..nv。

设生成函数为$F(x)=\sum_{i=0}^{\infty }x^{iv}$

则，对于一个s背包，ans=所有生成函数卷积，则复杂度为$O(n\log n)$。 对于[1,m]所有背包，复杂度为$O(mn\log n)$，也很爆炸

所以考虑生成函数的封闭形式来简化问题。

$$F(x)=\sum_{i=0}^{\infty }x^{iv}=\frac{1}{1-x^{v}}$$

那我们可以把封闭形式的求卷积，再来一个多项式求逆。 复杂度为$O(2^m)$，还是爆炸，那怎么办呢？

上面两种方法，都是因为卷积，如果我们能不乘法，而改为加法，那复杂度是不是可以了？

乘法变加法，取对数，多项式取$\ln$的复杂度也是$O(n\log n)$，那对所有的F(x)取，不是也会T吗？

先来看看这个多项式取$\ln$ 是什么形式。

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

$$G’(x)=\frac{F’(x)}{F(x)}$$

$$G’(x)=-\frac{-v*x^{v-1}}{1-x^{v}}$$

$$G’(x)=\frac{v*x^{v-1}}{1-x^v}$$

$$G’(x)=vx^{v-1}*\sum_{i=0}^{\infty} x^{iv}$$

$$G’(x)=v\sum_{i=0}^{\infty} x^{iv+v-1}$$

$$G(x)=v\sum_{i=0}^{\infty} \frac{x^{iv+v}}{iv+v}$$

$$G(x)=\sum_{i=0}^{\infty}\frac{x^{v(i+1)}}{i+1}$$

$$G(x)=\sum_{i=1}^{\infty}\frac{x^{iv}}{i}$$

所以我们可以先对每个物品的体积计数，然后分配给对应的$x^i$。

最后多项式exp得到原来多项式，并输出。

Code

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
##include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;

##define endl "\n"
##define eb emplace_back
##define mem(a, b) memset(a , b , sizeof(a))

const ll INF = 0x3f3f3f3f;
const ll mod = 998244353;
// const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
const double R = 0.57721566490153286060651209;

const int N = 4e5 + 10;

struct Complex {
    double x, y;
    Complex(double a = 0, double b = 0): x(a), y(b) {}
    Complex operator + (const Complex &rhs) { return Complex(x + rhs.x, y + rhs.y); }
    Complex operator - (const Complex &rhs) { return Complex(x - rhs.x, y - rhs.y); }
    Complex operator * (const Complex &rhs) { return Complex(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x); }
    Complex conj() { return Complex(x, -y); }
} w[N];

int tr[N];
ll EXP[N], V[N], ans[N];

ll quick_pow(ll a, ll b) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans % mod;
}

int getLen(int n) {
    int len = 1; while (len < (n << 1)) len <<= 1;
    for (int i = 0; i < len; i++) tr[i] = (tr[i >> 1] >> 1)  (i & 1 ? len >> 1 : 0);
    for (int i = 0; i < len; i++) w[i] = w[i] = Complex(cos(2 * PI * i / len), sin(2 * PI * i / len));
    return len;
}

void FFT(Complex *A, int len) {
    for (int i = 0; i < len; i++) if(i < tr[i]) swap(A[i], A[tr[i]]);
    for (int i = 2, lyc = len >> 1; i <= len; i <<= 1, lyc >>= 1)
        for (int j = 0; j < len; j += i) {
            Complex *l = A + j, *r = A + j + (i >> 1), *p = w;
            for (int k = 0; k < i >> 1; k++) {
                Complex tmp = *r * *p;
                *r = *l - tmp, *l = *l + tmp;
                ++l, ++r, p += lyc;
            }
        }
}

inline void MTT(ll *x, ll *y, ll *z, int len) {

    for (int i = 0; i < len; i++) (x[i] += mod) %= mod, (y[i] += mod) %= mod;
    static Complex a[N], b[N];
    static Complex dfta[N], dftb[N], dftc[N], dftd[N];

    for (int i = 0; i < len; i++) a[i] = Complex(x[i] & 32767, x[i] >> 15);
    for (int i = 0; i < len; i++) b[i] = Complex(y[i] & 32767, y[i] >> 15);
    FFT(a, len), FFT(b, len);
    for (int i = 0; i < len; i++) {
        int j = (len - i) & (len - 1);
        static Complex da, db, dc, dd;
        da = (a[i] + a[j].conj()) * Complex(0.5, 0);
        db = (a[i] - a[j].conj()) * Complex(0, -0.5);
        dc = (b[i] + b[j].conj()) * Complex(0.5, 0);
        dd = (b[i] - b[j].conj()) * Complex(0, -0.5);
        dfta[j] = da * dc;
        dftb[j] = da * dd;
        dftc[j] = db * dc;
        dftd[j] = db * dd;
    }
    for (int i = 0; i < len; i++) a[i] = dfta[i] + dftb[i] * Complex(0, 1);
    for (int i = 0; i < len; i++) b[i] = dftc[i] + dftd[i] * Complex(0, 1);
    FFT(a, len), FFT(b, len);
    for (int i = 0; i < len; i++) {
        ll da = (ll)(a[i].x / len + 0.5) % mod;
        ll db = (ll)(a[i].y / len + 0.5) % mod;
        ll dc = (ll)(b[i].x / len + 0.5) % mod;
        ll dd = (ll)(b[i].y / len + 0.5) % mod;
        z[i] = (da + ((ll)(db + dc) << 15) + ((ll)dd << 30)) % mod;
    }
}

void Get_Inv(ll *f, ll *g, int n) {
    if(n == 1) { g[0] = quick_pow(f[0], mod - 2); return ; }
    Get_Inv(f, g, (n + 1) >> 1);

    int len = getLen(n);
    static ll c[N];
    for(int i = 0;i < len; i++) c[i] = i < n ? f[i] : 0;
    MTT(c, g, c, len); MTT(c, g, c, len);
    for(int i = 0;i < n; i++) g[i] = (2ll * g[i] - c[i] + mod) % mod;
    for(int i = n;i < len; i++) g[i] = 0;
    for(int i = 0;i < len; i++) c[i] = 0;
}

void Get_Der(ll *f, ll *g, int len) { for(int i = 1;i < len; i++) g[i - 1] = f[i] * i % mod; g[len - 1] = 0; }

void Get_Int(ll *f, ll *g, int len) { for(int i = 1;i < len; i++) g[i] = f[i - 1] * quick_pow(i, mod - 2) % mod; g[0] = 0; }

void Get_Ln(ll *f, ll *g, int n) {
    static ll a[N], b[N];
    Get_Der(f, a, n);
    Get_Inv(f, b, n);
    int len = getLen(n);
    MTT(a, b, a, len);
    Get_Int(a, g, len);
    for(int i = n;i < len; i++) g[i] = 0;
    for(int i = 0;i < len; i++) a[i] = b[i] = 0;
}

void Get_Exp(ll *f, ll *g, int n) {
    if(n == 1) return (void)(g[0] = 1);
    Get_Exp(f, g, (n + 1) >> 1);

    static ll a[N];
    Get_Ln(g, a, n);
    a[0] = (f[0] + 1 - a[0] + mod) % mod;
    for(int i = 1;i < n; i++) a[i] = (f[i] - a[i] + mod) % mod;
    int len = getLen(n);
    MTT(a, g, g, len);
    for(int i = n;i < len; i++) g[i] = 0;
    for(int i = 0;i < len; i++) a[i] = 0;
}

void solve() {
    int n, m; cin >> n >> m;
    for(int i = 1;i <= n; i++) {
        int v; cin >> v;
        V[v]++;
    }

    for(int v = 1;v <= m; v++) {
        if(V[v]) {
            for(int i = 1;i <= m / v; i++) {
                EXP[i * v] = (EXP[i * v] + 1ll * V[v] * quick_pow(i, mod - 2)) % mod;
            }
        }
    }

    Get_Exp(EXP, ans, m + 1);

    for(int i = 1;i <= m; i++) cout << ans[i] << endl;

}

signed main() {
    ios_base::sync_with_stdio(false);
    // cin.tie(nullptr);
    // cout.tie(nullptr);
##ifdef FZT_ACM_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    signed test_index_for_debug = 1;
    char acm_local_for_debug = 0;
    do {
        if (acm_local_for_debug == '$') exit(0);
        if (test_index_for_debug > 20)
            throw runtime_error("Check the stdin!!!");
        auto start_clock_for_debug = clock();
        solve();
        auto end_clock_for_debug = clock();
        cout << "Test " << test_index_for_debug << " successful" << endl;
        cerr << "Test " << test_index_for_debug++ << " Run Time: "
             << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
        cout << "--------------------------------------------------" << endl;
    } while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
##else
    solve();
##endif
    return 0;
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/04/15/luogu-p4389/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！