思路：
考虑令\(f(x)\)表示从\(x\)到\(1\)的方案数，那么根据题意的两种操作可能，我们可以得到如下递推式
\(f(x) = \sum_{i=1}^{x-1}f(i) + \sum_{i=2}^{x}f(\frac{x}{i})\)，在简易版本中，也就是\(n\le2e5\)情况下，前面的和式很明显是前缀和优化，后面的和式可以用整除分块来在\(\sqrt{n}\)的时间内解决。
\(D1 - Up \ the \ Strip\ (simplified\ version)\)
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define MP make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lson rt<<1
#define rson rt<<1|1
#define CLOSE std::ios::sync_with_stdio(false)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-6;
const int N = 2e5 + 10;
ll n,p,g[N],dp[N];//g[i] 代表从2-i的所有到达1的方法数
void solve() {
scanf("%lld%lld",&n,&p);
dp[1] = 1,dp[2] = 2;
g[1] = 1,g[2] = 3;
for(ll i = 3;i <= n;i ++) {
dp[i] = g[i - 1];
for(ll l = 2,r = 0;l <= i;) {//r = n / (n / l)整除分块右端点位置
ll v = i / l;
r = i / v;
dp[i] = (dp[i] + dp[v] * (r - l + 1) % p) % p;
l = r + 1;
}
// cout << i << ": " << dp[i] << ‘\n‘;
g[i] = (g[i - 1] + dp[i]) % p;
// cout << i << ": " << g[i] << ‘\n‘;
}
printf("%lld\n",dp[n]);
}
int main() {
solve();
return 0;
}
\(D2 - Up \ the \ Strip\)
再看\(n\le4e6\)的情况下，如何解决。
令\(S(x)\)表示的是从\(x\)出发能够达到的所有点的集合(不去重)，考虑\(S(x+1)\)相较于\(S(x)\)其中集合内元素的变化情况，也就是他可以转移到的状态的变化情况。
对于减操作\(x+1\)会多一个\(f(x)\)的贡献，对于除操作会多一个\(1\)的贡献，然后如果\(i(i > 1)\)是\(x+1\)的因子，那么\(S(x+1)\)中就会用\(i\)这个数来替代\(S(x)\)中\(i-1\)这些数。
这样我们用一个\(sub\)标记来维护减操作的贡献，\(div\)操作来维护除操作的贡献。
对于数\(i\)，由上面的分析可知它会对\(t = 2i,3i,4i...,\)这些数带来一个变化，即\(f(t)\ += f(i) - f(i-1)\)，每次循环里面我只需要不断改变\(sub\)和\(div\)的值即可。
复杂度\(\frac{1}{n}+\frac{2}{n}+....+\frac{n}{n}\)，调和级数\(O(nlogn)\)。
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define MP make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lson rt<<1
#define rson rt<<1|1
#define CLOSE std::ios::sync_with_stdio(false)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-6;
const int N = 4e6 + 10;
ll dp[N],g[N],n,p;
void solve() {
scanf("%lld%lld",&n,&p);
// dp[1] = g[1] = 1;
ll sub = 0,div = 0;
for(ll i = 1;i <= n;i ++) {
if(i == 1) dp[i] = 1;
//到此 dp[i] 存的是 除部分从i-1到i的增量 因此加上 减的部分和i-1的除部分就是答案了
dp[i] = (dp[i] + sub + div) % p;
// dp[i] = (dp[i] + g[i-1]) % p;
for(int j = 2;i * j <= n;j ++) {
dp[i * j] = (dp[i * j] + dp[i] - dp[i-1] + p) % p;
}
if(i >= 2) div = (dp[i] - sub + p) % p;
sub = (sub + dp[i]) % p;
}
printf("%lld\n",dp[n]);
}
int main() {
solve();
return 0;
}