CodeForces 1558B Up the Strip

有 $n (2 \leq n \leq 4 \cdot 10^{6})$ 个节点，编号 $1 \sim n$ ，你一开始在节点 $n$ ，想要到节点 $1$ 。假设你现在在节点 $x$ ，你可以进行以下两种操作：

选择一个正整数 $y \in [1, x - 1]$ ，并移动到节点 $x - y$ 。
选择一个正整数 $z \in [2, x]$ ，并移动到节点 $⌊ \frac{x}{z} ⌋$ 。

求有多少种方案到达节点 $1$ ，只要有一次选择的 $x$ 或 $z$ 不同就算方案不同。答案对 $m$ 取模，其中 $m \in (10^{8}, 10^{9})$ 且 $m$ 是素数。

令 $f_{i}$ 表示 $n = i$ 时的答案，我们有：

f_{i} = \sum_{j = 1}^{i - 1} f_{j} + \sum_{d = 2}^{i} f_{⌊ \frac{i}{d} ⌋}

前一部分表示用减法，后一部分表示用除法。

考虑优化，第一部分直接前缀和，我们直接考虑第二部分。一种很直接的优化是将小于 $\sqrt{i}$ 的 $d$ 直接拿出来算，大于 $\sqrt{i}$ 的 $d$ 拿出来算贡献， $f_{k}$ 能转移到 $f_{i}$ 的 $d$ 应该满足 $k \leq \frac{i}{d} < k + 1$ ，也即 $\frac{i}{k + 1} < d \leq \frac{i}{k}$ ，于是 $f_{k}$ 对 $f_{i}$ 的贡献应该为 $⌊ \frac{n}{k} ⌋ - ⌊ \frac{n}{k + 1} ⌋$ 。这样做复杂度是 $O (n \sqrt{n})$ ，过不去，但是如果你打 Div. 2 的话就能过一个 easy 版。

我们考虑换一种方式，考虑 $f_{i}$ 转移到 $f_{i + 1}$ ，我们比较 $\sum_{d = 2}^{i} f_{⌊ \frac{i}{d} ⌋}$ 与 $\sum_{d = 2}^{i + 1} f_{⌊ \frac{i + 1}{d} ⌋}$ ，有如下变化：

多了一个 $f_{1}$ ，因为 $d$ 可以等于 $i + 1$ 。
对于所有 $d ∣ i + 1$ ， $⌊ \frac{i + 1}{d} ⌋ = ⌊ \frac{i}{d} ⌋ + 1$ ，所以 $f_{i + 1}$ 比 $f_{i}$ 多了一个 $f_{⌊ \frac{i + 1}{d} ⌋}$ ，少了一个 $f_{⌊ \frac{i}{d} ⌋}$ 。

也就是说：

\begin{aligned} f_{i + 1} & = \sum_{j = 1}^{i} f_{j} + \sum_{d = 2}^{i + 1} f_{⌊ \frac{i + 1}{d} ⌋} \\ = f_{i} + \sum_{j = 1}^{i - 1} f_{j} + \sum_{d = 2}^{i + 1} f_{⌊ \frac{i + 1}{d} ⌋} \\ = f_{i} + f_{i} + f_{1} + \sum_{d ∣ i + 1} (f_{⌊ \frac{i + 1}{d} ⌋} - f_{⌊ \frac{i}{d} ⌋}) \\ = 2 f_{i} + f_{1} + \sum_{d ∣ i + 1} (f_{⌊ \frac{i + 1}{d} ⌋} - f_{⌊ \frac{i}{d} ⌋}) \end{aligned}

我们发现对于所有 $i$ ，总的约数个数为 $\sum_{i = 1}^{n} \frac{n}{i} = O (n \log n)$ 。其余转移为 $O (n)$ ，故总复杂度为 $O (n \log n)$ 。

考虑实现，在每次计算出 $f_{i}$ 的时候，将所有的 $f_{k i}$ 都加上 $f_{i} - f_{i - 1}$ ，这样空间复杂度就是 $O (n)$ 。

cpp

const int maxn = 4000005;

int n, mod;

void add(int& x, int y) {
    x += y;
    if (x >= mod) {
        x -= mod;
    } else if (x < 0) {
        x += mod;
    }
}

int f[maxn];

int main() {
    read(n), read(mod);
    f[1] = 1;
    for (int i = 2; i <= n; ++i) {
        int tmp = f[i - 1] << 1 | 1;
        if (tmp >= mod) {
            tmp -= mod;
        }
        add(f[i], tmp);
        if (i == 2) {
            f[i] = 2;
        }
        for (int j = i << 1; j <= n; j += i) {
            add(f[j], f[i]);
            add(f[j], -f[i - 1]);
        }
    }
    writeln(f[n]);
    return 0;
}

Cite this post