CF1559E Mocha and Stars（dp+莫比乌斯反演）

求有多少长 $n$ 的序列 $a$ 满足：

• $l_i\le a_i\le r_i$
• ${\sum }_{i=1}^n{a}_i\le m$
• $\gcd (a_1,\dots ,a_n)=1$

答案对 $998244353$ 取模。

样例输入 #1

2 4
1 3
1 2
1
2
3

样例输出 #1

4
1

只看前两个条件，我们发现就直接是一个背包问题，枚举$a_i$，枚举背包状态，然后遍历所有的位置，时间复杂度是$O(m^{2}n)$,很显然，这个时间复杂度不能满足我们的要求，需要注意的是，题目问的是$<=m$。

dp[0]=1;//意义是：恰好等于下标的种类数
for(int i=1;i<=n;i++){
    memset(f,0,sizeof f);
    for(int j=l[i];j<=r[i];j++){
        for(int k=j;k<=m;j++){
            f[k]+=dp[k-j];
        }
    }
    dp[0]=0;
    for(int j=1;j<=m;j++)dp[i]=dp[i]+f[i];
}
1
2
3
4
5
6
7
8
9
10
11

但是其实我们发现，中间的状态转移，用前缀和就可以完美解决

for(int i=0;i<=m;i++)dp[i]=1;//意义是：小于等于下标的种类数（因此使用前缀和）
for(int i=1;i<=n;i++){
    memset(f,0,sizeof f);
    for(int j=l[i];j<=m;j++){
        f[j]+=dp[j-l[i]];
        if(j>r[i]){
            f[j]-=dp[j-r[i]-1];//要[l[i],r[i]]区间的数，大于r[i]的数无法转移，因此减掉
        }
    }
    dp[0]=0;
    for(int j=1;j<=m;j++)dp[i]=dp[i-1]+f[i];
}
1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度是$O(nm)$还可以~

于是现在求的问题就是

$\sum _{a_1=l[1]}^{r[1]}\sum _{a_2=l[2]}^{r[2]}...\sum _{a_n=l[n]}^{r[n]}f(a_1,a_2...a_n)\ast [gcd(a_1,a_2...a_n)=1]$

转换一下

$\sum _{a_1=l[1]}^{r[1]}\sum _{a_2=l[2]}^{r[2]}...\sum _{a_n=l[n]}^{r[n]}f(a_1,a_2...a_n)\ast \epsilon (gcd(a_1,a_2...a_n)=1)$

展开

$\sum _{a_1=l[1]}^{r[1]}\sum _{a_2=l[2]}^{r[2]}...\sum _{a_n=l[n]}^{r[n]}f(a_1,a_2...a_n)\ast \sum _{d|gcd(a_1,a_2...a_n)}\mu (d)$

交换枚举顺序

$\sum _{d=1}^m\mu (d)\sum _{a_1=l[1]/d}^{r[1]/d}\sum _{a_2=l[2]/d}^{r[2]/d}...\sum _{a_n=l[n]/d}^{r[n]/d}f(a_1\ast d,a_2\ast d...a_n\ast d)$

枚举倍数是调和级数，时间复杂度是$O(lnm)$，枚举$n$个数，那么时间复杂度是$nlnm$，前面的$d$枚举起来是$m$，因此时间复杂度是$O(nmlnm)$

#include 
using namespace std;
const int N = 500005;
const int mod = 998244353;
int check[N + 5], n, m;
int mu[N + 5], p[N + 5];
bool flg[N + 5];
int dp[N];
int l[N];
int r[N];
void mobius()
{
    int tot = 0;
    mu[1] = 1;
    for (int i = 2; i <= N; ++i)
    {
        if (!flg[i])
        {
            p[++tot] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= tot && i * p[j] <= N; ++j)
        {
            flg[i * p[j]] = 1;
            if (i % p[j] == 0)
            {
                mu[i * p[j]] = 0;
                break;
            }
            mu[i * p[j]] = -mu[i];
        }
    }
}
signed main()
{
    mobius();
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> l[i] >> r[i];
    int ans = 0;

    for (int d = 1; d <= m; d++)
    {
        if (!mu[d])
            continue;
        int tot = 0;
        int sum = m / d;
        vector<int> dp(sum + 1, 1);
        for (int i = 1; i <= n; i++)
        {
            vector<int> f(sum + 1);
            for (int j = (l[i] + d - 1) / d; j <= sum; j++)
            {
                f[j] = dp[j - (l[i] + d - 1) / d];
                if (j >= r[i] / d + 1)
                    f[j] = (f[j] - dp[j - r[i] / d - 1] + mod) % mod;
            }
            dp[0] = 0;
            for (int j = 1; j <= sum; j++)
                dp[j] = (dp[j - 1] + f[j]) % mod;
        }
        ans = ((ans + dp[sum] * mu[d]) % mod + mod) % mod;
    }
    cout << ans << endl;
}
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