GYM103415K Magus Night

Solution
1012 Words

简要题意

对所有长度为 $n$ ，元素不超过 $m$ ，$\texttt{lcm} \ge p$，$\texttt{gcd} \le q$ 数列求积的和

分析

原题意可转化为全部 数列的贡献去掉$\texttt{lcm} < p$、$\texttt{gcd} > q$，再加上 $\texttt{lcm} < p$，$\texttt{gcd} > q$ 数列的贡献

第一部分我们考虑二（多）项式定理，故总和为$H(m)=(\sum_{i=1}^mi)^n=(\frac{m(m+1)}{2})^n$

第二部分我们考虑枚举 $\texttt{lcm}$ ，设 $g(x)$ 表示 $\texttt{lcm}=x$ 数列的贡献

则可以莫比乌斯反演，$g(x)=\sum_{d|x} \mu(d) h(\frac{x}{d})$， 其中 $h(x)$ 是所有 $\texttt{lcm}$ 为 $x$ 因数的数列的贡献

$h(x)$ 的表达式可以写成 $(\sum_{i|x}i)^n$ ，于是我们就可以愉快计算 $g(x)$ 了

第三部分同样考虑枚举 $\texttt{gcd}$，设 $G(x)$ 表示 $\texttt{gcd}=x$ 数列的贡献

考虑把 $x$ 除掉变成互质数列，互质数列贡献 $F(m)=\sum_{d=1}^x \mu(d) H(\frac{m}{d})$（好像这里可以整除分块？）

则 $G(x)=x^n F(\frac{m}{x})$ ，于是也可以快乐计算 $G(x)$ 了

第四部分考虑同时枚举 $\texttt{gcd}$ 和 $\texttt{lcm}$，由于 $\texttt{lcm} < p$，且 $\texttt{gcd}$ $\mid$ $\texttt{lcm}$，故这里复杂度是正确的

先考虑一个$\texttt{gcd} = 1, \texttt{lcm}=x$ 的数列，它的贡献 $f(x)=\sum_{d|x} \mu(d) g(\frac{x}{d})$

再考虑一个$\texttt{gcd}=t$ 和 $\texttt{lcm}=xt$ 的数列，则 $f(x)$ 只要乘上 $t^n$ 即可

综上所述，总贡献为
$$
ans=H(m)-\sum_{x=1}^{p-1}g(x)-\sum_{t=q+1}^{m}G(t)+\sum_{t=q+1}^m \sum_{x=1}^{\frac{p-1}{t}}t^nf(x)
$$

代码

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
#include <bits/stdc++.h>
#define R register
#define ll long long
#define meow(cat...) fprintf(stderr, cat)

const ll MaxN = 2e5 + 10;
const ll mod = 998244353;
const ll inv2 = (mod + 1) / 2;

std::vector<ll> d[MaxN];
ll n, m, p, q, cnt, ans, f[MaxN], g[MaxN], h[MaxN], pw[MaxN], mu[MaxN];
ll vis[MaxN], s[MaxN], pr[MaxN], F[MaxN], G[MaxN], H[MaxN];

ll sum(ll a, ll b) { return ((a + b) % mod + mod) % mod; }
ll Add(ll &a, ll b) { return a = sum(a, b); }

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

void init()
{
    mu[1] = 1;
    for(ll i = 2; i < MaxN; i++)  
    {
        if(!vis[i]) pr[++cnt] = i, mu[i] = -1;
        for(ll j = 1; j <= cnt && i * pr[j] < MaxN; j++)
        {
            vis[i * pr[j]] = 1;
            if(i * pr[j] == 0)
                { mu[i * pr[j]] = 0; break; }
            mu[i * pr[j]] = -mu[i];
        }
    }
    for(ll i = 1; i < MaxN; i++)
        s[i] = sum(s[i - 1], mu[i]), Add(s[i], mod);
}

inline ll read()
{
    ll x = 0;
    char ch = getchar();
    while(ch > '9' || ch < '0')
        ch = getchar();
    while(ch <= '9' && ch >= '0') 
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}

signed main()
{   
    n = read(), m = read(), p = read(), q = read(), init();
    for(ll i = 1; i <= m; i++)
        H[i] = i * (i + 1) % mod * inv2 % mod, H[i] = fast_pow(H[i], n); 
    for(ll i = 1; i <= m; i++)
        for(ll j = 1; j * j <= i; j++)
            if(i % j == 0)
            {
                d[i].push_back(j);
                if(j * j != i)
                    d[i].push_back(i / j);
            }
    // meow("1 %d\n", clock());
    for(ll i = 1; i <= m; i++)
    {
        pw[i] = fast_pow(i, n);
        for(ll j = 0; j < d[i].size(); j++)
            Add(h[i], d[i][j]);
        // printf("$ %lld %lld\n", i, h[i]);
        h[i] = fast_pow(h[i], n);
    }
    // meow("2 %d\n", clock());
    for (ll i = 1; i <= m; i++) 
    {
        g[i] = h[i];
        for (auto j : d[i]) 
        {
            if (j == i) continue;
            Add(g[i], mod - g[j]);
        }
    }
    // meow("3 %d\n", clock());
    // meow("4 %d\n", clock());
    // for(ll i = 1; i <= m; i++)
    // {
    //     printf("i: %d ", i);
    //     for(ll l = 1, r; l <= i; l = r + 1)
    //         r = i / (i / l), Add(F[i], sum(s[r], mod - s[l - 1]) * H[i / r] % mod), 
    //             printf("%d %d %d | ", l, r, i / l);
    //     puts("");
        
    // }
    for (int i = m; i >= 1; --i) 
    {
        F[i] = H[m / i] * pw[i] % mod;
        for (int j = i + i; j <= m; j += i) 
        Add(F[i], mod - F[j]);
    }
    // meow("5 %d\n", clock());
    for(ll i = 1; i <= m; i++)
        G[i] = (F[i] % mod + mod) % mod;
    ll res1 = 0, res2 = 0, res3 = 0;
    for(ll x = 1; x < p; x++) Add(res1, g[x]);
    // meow("6 %d\n", clock());
    for(ll t = q + 1; t <= m; t++) Add(res2, G[t]);
    // for(ll i = 1; i <= m; i++)
    //     for(ll j = 1; i * j <= m; j++)
    //         Add(f[i * j], g[i] * mu[j]);        
    // for(ll t = q + 1; t < p; t++)
    //     for(ll x = 1; x <= (p - 1) / t; x++)
    //         Add(res3, pw[t] * f[x] % mod);
    for (int i = 1; i <= m; i++)
        g[i] = sum(g[i], g[i - 1]);
    for (int i = q + 1; i < p; i++)
        f[i] = g[(p - 1) / i] * pw[i] % mod;
    for (int i = p - 1; i > q; i--)
    {
        for (int j = 2 * i; j < p; j += i)
            f[i] = sum(f[i], mod - f[j]);
        res3 = sum(res3, f[i]);
    }
    // meow("7 %d\n", clock());
    ans = ((H[m] - res1 - res2 + res3) % mod + mod) % mod;
    meow("%lld %lld %lld %lld %lld\n", H[m], res2, res1, res3, ans); 
    printf("%lld\n", ans);
    return 0;
}
数论, 莫比乌斯反演
New Beginning
CF1601B Frog Traveler
关注我

分类

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×