Dyd's Blog

He who has a strong enough why can bear almost any how.

luoguP4389 付公主的背包

Posted on In
Symbols count in article: 3.5k Reading time ≈ 3 mins.

套路对数化连乘为连加

付公主的背包

思路

显然 OGF ，我们要求：
$$
\begin{aligned}
F(x)
= &\prod (1 + x^{v_i} + x^{2v_i} + …) \\
= & \prod \frac{1}{1 - x^{v_i}} \\
\end{aligned}
$$
求对数，有：
$$
\begin{aligned}
G(x) = & \ln(F(x)) \\
= & \sum \ln(\frac{1}{1 - x^{v_i}}) \\
\end{aligned}
$$
问题是求 $\ln(\frac{1}{1 - x^{v_i}})$ ：
$$
\begin{aligned}
& \ln(\frac{1}{1 - x^v}) \\
= & - \ln (1 - x^v) \\
求导得: \\
(\ln(1 - x^v))’ = & \frac{-v x^{v - 1}}{1 - x^v} \\
= & -v x^{v - 1} (1 + x^{v} + x^{2v} + …) \\
= & -v(x^{v - 1} + x^{2v - 1} + x^{3v - 1} + …) \\
再积分回去得: \\
\ln(1 - x^v) = & -v(\frac{1}{v}x^v + \frac{1}{2v}x^{2v} + … ) \\
= & \sum -\frac{1}{i} x^{iv} \\
则: \\
\ln(\frac{1}{1 - x^v}) = & \sum \frac{1}{i} x^{iv} \\
\end{aligned}
$$
于是构造出多项式然后 $\exp$ 一下即可

代码

注意 $v_i$ 有重复，直接做会 TLE ，要开桶把相同的 $v_i$ 一起做

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
#include <vector>
#include <cstdio>
#define si size()
#define rsi resize
using LL = long long;
using poly = std::vector<int>;
const int N = 1 << 18 | 100, G = 3, P = 998244353;
int n, m, iv[N], rev[N], b[N];
void adj(int &x){ x += (x >> 31) & P; }
int qpow(int x, int y = P - 2)
{
    if (y == P - 2 && x < N) return iv[x];
    int res = 1;
    for (; y; y >>= 1, x = LL(x) * x % P) if (y & 1) res = LL(res) * x % P;
    return res;
}
void rdy(int &bit, int &tot, int len){ for (bit = 0, tot = 1; tot <= len; tot <<= 1, ++bit); }
void get_r(int bit, int tot){ for (int i = 1; i < tot; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1)); }
void ntt(int *x, int tot, int op)
{
    static int gn[N];
    for (int i = 1; i < tot; ++i) if (i < rev[i]) std::swap(x[i], x[rev[i]]);
    for (int mid = 1; mid < tot; mid <<= 1)
    {
        int g0 = qpow(G, (P - 1) / (mid << 1));
        if (op == -1) g0 = qpow(g0);
        gn[0] = 1;
        for (int i = 1; i < mid; ++i) gn[i] = LL(g0) * gn[i - 1] % P;
        for (int i = 0; i < tot; i += (mid << 1))
            for (int *x1 = x + i, *x2 = x + i + mid, *ed = x2, *g = gn; x1 != ed; ++x1, ++x2, ++g)
            {
                int p = *x1, q = LL(*x2) * *g % P;
                adj(*x1 = p + q - P), adj(*x2 = p - q);
            }
    }
    if (op == 1) return ;
    int t = qpow(tot);
    for (int i = 0; i < tot; ++i) x[i] = LL(t) * x[i] % P;
}
poly operator * (poly x, poly y)
{
    if (x.empty() || y.empty()) return {};
    int n = x.si, m = y.si, tot, bit;
    rdy(bit, tot, n + m), get_r(bit, tot);
    x.rsi(tot), y.rsi(tot);
    if (x == y) ntt(x.data(), tot, 1), y = x;
    else ntt(x.data(), tot, 1), ntt(y.data(), tot, 1);
    for (int i = 0; i < tot; ++i) x[i] = LL(x[i]) * y[i] % P;
    ntt(x.data(), tot, -1);
    return x.rsi(n + m - 1), x;
}
poly operator - (poly x, poly y)
{
    if (x.si < y.si) x.rsi(y.si);
    for (int i = y.si - 1; ~i; --i) adj(x[i] -= y[i]);
    return x;
}
poly inv(poly x)
{
    int n = x.si;
    if (n == 1) return {qpow(x[0])};
    poly y = inv(poly(x.begin(), x.begin() + ((n + 1) >> 1))), z = y * y * x, res(n);
    y.rsi(n), z.rsi(n);
    for (int i = 0; i < n; ++i) adj(res[i] = 2 * y[i] - z[i]);
    return res;
}
poly dif(poly x)
{
    poly res(x.si - 1);
    for (int i = x.si - 1; i; --i) res[i - 1] = LL(i) * x[i] % P;
    return res;
}
poly inte(poly x)
{
    poly res(x.si + 1);
    for (int i = x.si - 1; ~i; --i) res[i + 1] = LL(x[i]) * iv[i + 1] % P;
    return res;
}
poly ln(poly x)
{
    poly res(inv(x) * dif(x));
    res.rsi(x.si), res = inte(res);
    return res.rsi(x.si), res;
}
poly exp(poly x)
{
    int n = x.si;
    if (n == 1) return {1};
    poly y = exp(poly(x.begin(), x.begin() + ((n + 1) >> 1)));
    y.rsi(n);
    poly z = ln(y);
    x = x - z, ++x[0], x = x * y;
    return x.rsi(n), x;
}
int main()
{
    iv[1] = 1;
    for (int i = 2; i < N; ++i) iv[i] = LL(P - P / i) * iv[P % i] % P;
    scanf("%d %d", &n, &m);
    poly f(m + 1);
    for (int i = 1, v; i <= n; ++i) scanf("%d", &v), ++b[v];
    for (int i = 1; i <= m; ++i) if (b[i])
        for (int j = 1; i * j <= m; ++j) adj(f[i * j] += LL(iv[j]) * b[i] % P - P);
    f = exp(f);
    for (int i = 1; i <= m; ++i) printf("%d\n", f[i]);
    return 0;
}