【题解】CF1559E Mocha and Stars

题目：​​Codeforces 链接​​  &  ​​Luogu 链接​​

如果只看前两个条件，那么这是一个比较显然的背包问题。

令 $f_{i,j}$ 表示前 $n$ 个数 $a_i$ 总和为 $j$ 的方案数。

那么对于每个 $a_i=l_i \sim r_i$ 均有

$$f_{i,j}=\sum_{k=l_i}^{r_i} f_{i-1,j-k}$$

当然直接上背包复杂度是 $\mathcal{O}(nm^2)$ 级别的，我们需要把每一个 $i$ 的所有 $f_{i,j}$ 记录一个前缀和。记

$$s_{i,j}=\sum_{k=0}^{j}f_{i,k}$$

且当 $j<0$ 时 $s_{i,j}=0$。

那么有可以一次性转移的方程：

$$f_{i,j}=s_{i-1,j-l_i}-s_{i-1,j-r_i-1}$$

时间复杂度降为了 $\mathcal{O}(nm)$。

之后就是最后一个条件：$\gcd(a_1,a_2,...,a_n)=1$。

这可以让人联想到许多数论题目的常见解决办法，比如莫比乌斯反演或者容斥，这里讲讲容斥做法。

设

$$F(x)=\sum_{a_1=l_1}^{r_1}\sum_{a_2=l_2}^{r_2}...\sum_{a_n=l_n}^{r_n}[\gcd(a_1,a_2,...,a_n)=x]\left[\sum_{i}a_i \le m\right]$$

显然我们最后要求 $F(1)$。

观察到这个式子仍比较麻烦，但是条件转化成 $[x \mid \gcd(a_1,a_2,...,a_n)]$ 的话问题就会好做点。

于是再定义 $G(x)=\sum\limits_{d=1}^{\lfloor\frac{m}{x}\rfloor}F(dx)$，相当于

$$G(x)=\sum_{a_1=l_1}^{r_1}\sum_{a_2=l_2}^{r_2}...\sum_{a_n=l_n}^{r_n}[x \mid \gcd(a_1,a_2,...,a_n)]\left[\sum_{i}a_i \le m\right]$$

然后 $[x \mid \gcd(a_1,a_2,...,a_n)]$ 这个条件就等价于限制了每个 $a_i$ 都是 $x$ 的倍数。

那我们在枚举 $a_i$ 的时候直接强制它是 $x$ 的倍数，就消去 $\gcd=1$ 的条件，可以直接上背包了。

之后还没完，我们要算的是 $F(1)$，但只求出了 $G(x)$。

观察一下 $G(x)$ 的定义式

$$G(x)=\sum_{d=1}^{\lfloor\frac{m}{x}\rfloor}F(dx)$$

移个项：

$$F(x)=G(x)-\sum_{d=2}^{\lfloor\frac{m}{x}\rfloor}F(dx)$$

那么我们从 $m$ 到 $1$ 倒序枚举 $x$，$G(x)$ 用背包求，且所有的 $F(x)$ 都可以求出来。

在枚举 $x$ 和 $x$ 的倍数这一步骤，时间复杂度为调和级数级别的，大约为 $\mathcal{O}(m \ln m)$。

因此均摊到每个 $x$ 的时间复杂度为 $\mathcal{O}(\ln m)$

对于每个 $G(x)$，我们可以用背包求。枚举 $x$ 的倍数也不怎么方便，所以我们可以将上下界以及 $m$ 都除掉 $x$，这样就可以使得 $a_i$ 连续，且减小背包容量，优化时间复杂度。

对于每个 $G(x)$，背包容量可以降为 $\lfloor\frac{m}{x}\rfloor$。

上文说了，$\sum\limits_{i=1}^m\frac{m}{x}=\mathcal{O}(m \ln m)$。

因此该做法总复杂度为 $\mathcal{O}(nm \ln m)$。

说一下写代码时的注意点：

• 前缀和数组的初始值为 $0$。
• 注意方式背包时下标变负数的情况。
• 做除法的时候，注意下界 $\frac{l_i}{x}$ 要上取整。
• 取模要取干净。

这道题就这么做完了。具体细节可以看代码：

#include <bits/stdc++.h>
#define N 100010
#define MOD 998244353
#define reg register
typedef long long ll;
using namespace std;

int n, m, l[N], r[N], dp[N], las[N], ss[N], ans, sss, slas[N];

inline int F(int x, int y){        // 上取整
    return x / y + (x % y != 0);
}

int main(){

    cin >> n >> m;
    for(reg int i = 1; i <= n; i++) cin >> l[i] >> r[i];
    for(reg int d = m; d >= 1; d--){
        for(reg int j = 0; j <= m / d; j++)
            dp[j] = 0, las[j] = 0, slas[j] = 0;
        las[0] = slas[0] = 1;
        for(reg int j = 1; j <= m / d; j++)
            slas[j] = (slas[j - 1] + las[j]);
        for(reg int j = 1; j <= n; j++){
            for(reg int L = m / d; L >= F(l[j], d); L--){
                if(L - r[j] / d > 0) dp[L] = (slas[L - F(l[j], d)] - slas[L - r[j] / d - 1] + MOD) % MOD;
                else dp[L] = slas[L - F(l[j], d)];
            }
            for(reg int j = 0; j <= m / d; j++)
                las[j] = dp[j], dp[j] = 0;
            slas[0] = las[0];
            for(reg int j = 1; j <= m / d; j++)
                slas[j] = (slas[j - 1] + las[j]) % MOD;
        }
        for(reg int j = 0; j <= m / d; j++)
            ss[d] = (ss[d] + las[j]) % MOD;
        for(reg int j = d + d; j <= m; j += d)
            ss[d] = (ss[d] - ss[j] + MOD) % MOD;
    }
    printf("%d\n", ss[1]);

    return 0;
}