CF1561D1 题解

link

你有一个数 $n$，问有多少种执行一下操作的方案，使 $n$ 变成 $1$

• 将 $n$ 减去一个在 $[1, x)$ 的值 $x$

• 将 $n$ 除以一个 $(1, x]$ 的值并向下取整。

注意减或除的 $x$ 不一样方案也不同，方案数对质数 $m$ 取模。

$2 \le n \le 2 \times 10^5, \ 10^8 < m < 10^9, \ m \in prime$

为什么不直接写 D2 题解，因为我不会呀.

设 $f_i$ 表示 $n = i$ 时的答案。显然

$$f_i = \sum_{j=1}^{x-1} f_j + \sum_{j=2}^x f_{\lfloor\dfrac{i}{j}\rfloor}$$

前面减的部分可以直接前缀和算，问题是后面部分。

然后的形式非常是整除分块的形式，可以用整除分块 $O(\sqrt{n})$ 求。

时间复杂度 $O(n\sqrt{n})$。

CODE

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
inline int read() {
    int x = 0, f = 0; char c = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = getchar();
    return f ? -x : x;
}
 
#define N 200010
 
int n, P, f[N];
 
signed main() {
    n = read(), P = read();
    f[1] = 1;
    int now = 1;
    for (int i = 2; i <= n; i ++) {
        f[i] = now;
        for (int l = 2, r; l <= i; l = r + 1) {
            r = i / (i / l);
            (f[i] += (r - l + 1) % P * f[i / l] % P) %= P;
        }
        now = (now + f[i]) % P;
    }
    printf("%lld\n", f[n]);
    return 0;
}