DDOSvoid's Blog

CF 1559E Mocha and Stars

发表于 分类于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

题目描述

https://codeforces.com/problemset/problem/1559/E

简要题意：给定 $n$ 和 $n$ 个区间 $[l_i,r_i]$ 以及一个整数 $m$，求有多少长度为 $n$ 的序列 $a_i$ 满足 $l_i\le a_i\le r_i$ 且 $\sum_{i=1}^na_i\le m$ 且 $gcd(a_1,\cdots,a_n)=1$

$n\le 50,m\le 10^5,l_i\le r_i\le m$

Solution

我们考虑直接容斥，每次计算 $gcd$ 是 $d$ 的倍数的方案，最后拿 $\mu$ 容斥一下即可，所以我们枚举 $d$，注意对于 $d=1$ 的 $dp$ 我们可以通过前缀和优化做到 $O(nm)$，那么对于 $d$ 不等于 $1$，我们也可以做到 $O(\lfloor\frac{nm}{d}\rfloor)$，那么总时间复杂度 $O(nm\log m)$，另外需要注意 $[l_i,r_i]$ 对于 $d$ 能选的数的个数为 $[\lceil \frac{l_i}{d}\rceil,\lfloor\frac{r_i}{d}\rfloor]$

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
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <numeric>
#define maxn 100010
#define maxm 51
#define ll long long
using namespace std;

const int p = 998244353;
inline int add(int x, int y) { return (x += y) >= p ? x - p : x; }
inline int mul(int x, int y) { return 1ll * x * y % p; }
inline int add(initializer_list<int> lst) { int s = 0; for (auto t : lst) s = add(s, t); return s; }
inline int mul(initializer_list<int> lst) { int s = 1; for (auto t : lst) s = mul(s, t); return s; }

int pri[maxn], mu[maxn]; bool isp[maxn];
void init_isp(int n) {
    mu[1] = 1; int cnt = 0; 
    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) pri[++cnt] = i, mu[i] = p - 1;
        for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
            isp[i * pri[j]] = 1;
            if (i % pri[j] == 0) break;
            mu[i * pri[j]] = p - mu[i];
        }
    }
}

int n, m, l[maxn], r[maxn];

int dp[maxm][maxn];
int f[maxn];

inline int get_sum(int k, int l, int r) {
    if (r < 0) return 0;
    if (l <= 0) return dp[k][r];
    return add(dp[k][r], p - dp[k][l - 1]);
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; init_isp(m);
    for (int i = 1; i <= n; ++i) cin >> l[i] >> r[i];
    for (int i = 0; i <= m; ++i) dp[0][i] = 1; 
    for (int d = 1; d <= m; ++d) {
        bool ok = true; if (!mu[d]) continue;
        for (int i = 1; i <= n; ++i)
            if ((l[i] + d - 1) / d > r[i]) ok = false;
        if (!ok) break;
        for (int i = 1; i <= n; ++i) 
            for (int j = 0; j <= m / d; ++j) { 
                dp[i][j] = get_sum(i - 1, j - r[i] / d, j - (l[i] + d - 1) / d);
                if (j) dp[i][j] = add(dp[i][j], dp[i][j - 1]);
            }
        f[d] = dp[n][m / d];
    } int ans = 0; for (int i = 1; i <= m; ++i) ans = add(ans, mul(mu[i], f[i]));
    cout << ans << "\n";
    return 0;
}