D1. Up the Strip (simplified version)
思路:
考虑正着推,
f[i] 表示 1 到i号点的方案
属性:cnt
状态计算:因为i号点 能到达 [1, i - 1] 号点 那么反过来 [1, i - 1] 可到达i号点,
i号点也能到达[i / 2] [i / 3] [i / i] 号点 同理 [i / 2] [i / 3] [i / i] 也可到达i号点
状态转移方程
$$ f[i] = \sum_{k = 1} ^ {i - 1} f[k] + \sum_{k = 2} ^ {i} f[i / k] $$
观察式子可以发现 可以利用前缀和 和 整除分块(下取整又是求区间)优化
$$时间复杂度 n \sqrt{n} $$
整除分块
整除分块就是把n除以每一个i的商相同的分成一块,枚举[l, r]区间即对于该分块区间任意一个数来说
n / r = n / l 得到 r = n / n / l
$$ \sum_ {i = 1} ^ {n} \lfloor {n / i} \rfloor $$
for(ll l = 1, r;l <= n; l = r + 1)
{
r = n / (n / l);
ans += (r - l + 1) * (n / l);
}
C++ 代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 3e5 + 10;
typedef pair <int, int> PII;
ll f[maxn], sum[maxn];
int main()
{
int n,m;
scanf("%d %d", &n, &m);
f[1] = 1;
for(int i = 1 ; i <= n ; i ++)
{
f[i] += sum[i - 1];
f[i] %= m;
for(int l = 2, r = 0; l <= i; l = r + 1)
{
r = i / (i / l);
f[i] += (r - l + 1) * f[i / l];
f[i] %= m;
}
sum[i] = sum[i - 1] + f[i];//
sum[i] %= m;
}
printf("%lld\n", f[n] % m);
return 0;
}