CF1559E Mocha and Stars

题意翻译

求有多少长 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 取模。

Solution

答案求
\sum_{a_1=l_1}^{r_1}\sum_{a_2=l_2}^{r_2}\dots\sum_{a_n=l_n}^{r_n}[(a_1,a_2,\dots,a_n)=1][\sum_{i=1}^na_i\leq m]
考虑引入莫比乌斯反演

f(d)=\sum_{a_1=l_1}^{r_1}\sum_{a_2=l_2}^{r_2}\dots\sum_{a_n=l_n}^{r_n}[(a_1,a_2,\dots,a_n)=d][\sum_{i=1}^na_i\leq m]

那么

F(n)=\sum_{n|d}f(d)=f(d)=\sum_{a_1=l_1}^{r_1}\sum_{a_2=l_2}^{r_2}\dots\sum_{a_n=l_n}^{r_n}[n|(a_1,a_2,\dots,a_n)][\sum_{i=1}^na_i\leq m]

F(n)=\sum_{a_1=\lceil \frac{l_1}{n}\rceil}^{\lfloor \frac{r_1}{n}\rfloor}\dots\sum_{a_n=\lceil \frac{l_n}{m}\rceil}^{\lfloor \frac{r_n}{n}\rfloor}[\sum_{i=1}^na_i\leq \lfloor \frac{m}{n}\rfloor]

可以看出 F(n) 可以利用背包+前缀和优化求解

于是 ans=f(1)=\sum_{d=1}^m\mu(d)F(d)

#include<bits/stdc++.h>
#define ll long long
const ll mod = 998244353;
const int N = 1e5+10;
bool vis[N];
int prime[N],Mob[N],g[N];
int n,m,l[55],r[55];
ll s[55][N],dp[55][N];
void Mobius_sieve(){
    int cnt = 0;
    vis[1] = 1;
    Mob[1] = 1;
    for(int i = 2; i < N; i++){
        if(!vis[i])
            prime[cnt++] = i, Mob[i] = - 1 , g[i] = 1;
        for(int j = 0; j < cnt && 1LL * prime[j] * i < N; j++){
            vis[prime[j] * i] = 1;
            g[prime[j]*i] = g[i] + 1;
            Mob[i * prime[j]] = (i % prime[j] ? -Mob[i]: 0);
            if(i % prime[j] == 0)
                break;
        }
    }
}
ll F(int x){
    for(int i=1;i<=n;++i){
        int L = l[i]/x+((l[i]%x)!=0) , R = r[i]/x;
        for(int j=1;j<=m/x;++j){
            ll X = j-L>=0 ? s[i-1][j-L]:0;
            ll Y = j-R-1>=0 ? s[i-1][j-R-1]:0;
            dp[i][j]=((X-Y)%mod+mod)%mod;
            s[i][j]=(s[i][j-1]+dp[i][j])%mod;
        }
    }
    return s[n][m/x];
}
int main(){
    Mobius_sieve();
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d%d",&l[i],&r[i]);
    ll ans = 0 ;
    for(int i=0;i<=m;++i)
        s[0][i] = 1; 
    for(int i=1;i<=m;++i)
        ans += 1ll*Mob[i]*F(i)%mod,ans%=mod;
    printf("%lld",(ans+mod)%mod);
}

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注