题意：你有一个由\(n\)个网格组成的竖直列，每个网格中依次有数字\(1,2，\cdots, n\)。初始时你在位置\(n\)?，每次你可以执行以下操作中的某一种：

1、跳到任意一个数字比当前位置小的位置

2、假设当前位置为\(i\), 选择一个整数\(x,x\in[2,i]\)，你可以跳到\(\lfloor\frac{i}{x}\rfloor\)

求有多少种方案能从\(n\)?跳到\(1\)??. 方案不同当且仅当操作对应的序列不同

D1中\(n\)的数据范围为2e5, D2中为4e6

sol.

第一种操作直接前缀和就行，第二种操作可以考虑对每个\(i\)?整除分块求解答案。

D1的ac代码如下

// Problem: D1. Up the Strip (simplified version)
// Contest: Codeforces - Codeforces Round #740 (Div. 2, based on VK Cup 2021 - Final (Engine))
// URL: https://codeforces.com/contest/1561/problem/D1
// Memory Limit: 128 MB
// Time Limit: 6000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e6 + 7;
#define ll long long
int rd() {
    int s = 0, f = 1; char c = getchar();
    while (c < ‘0‘ || c > ‘9‘) {if (c == ‘-‘) f = -1; c = getchar();}
    while (c >= ‘0‘ && c <= ‘9‘) {s = s * 10 + c - ‘0‘; c = getchar();}
    return s * f;
}
ll n, m, k, tot, f[maxn], sum = 1, sumg, lst = 1;
int main() {
	n = rd(); m = rd();
	f[1] = 1;
	for (int i = 2; i <= n; i++) {
		f[i] += sum; f[i] %= m;
		sumg = 1;
		for (int l = 1, r; l <= i; l = r + 1) {
			k = i / l;
			r = i / k;
			//printf("l, r, k== %d %d %lld\n", l, r, k);
			if (k == i) continue;
			f[i] = (f[i] + f[k] * (r-l+1) % m) % m;
			lst = r;
		}
		sum = (sum + f[i]) % m;
	}
	//for (int i = 1; i <= n; i++) printf("f[%d]==%d\n", i, f[i]);
	printf("%lld\n", f[n] % m);
	return 0;
}	

对于D2，\(n\le 4e6\)，\(\lfloor\frac{i}{x} \rfloor=k \lrarr xk \le i \le xk + x - 1\)，枚举\(k\)，那么\(f(k)\)能对\(f(k+1),f(k+2),\cdots,f(n)\)以及\(f(i),xk \le i \le xk + x - 1\)产生贡献。

如果把dp式子倒过来，改成从1转移到n，操作分别改为上述转移，那么最终的方案数是一样的。

枚举\(x\)?及其倍数，后缀和优化，复杂度为\(O(n\ln n)\)?.

// Problem: D1. Up the Strip (simplified version)
// Contest: Codeforces - Codeforces Round #740 (Div. 2, based on VK Cup 2021 - Final (Engine))
// URL: https://codeforces.com/contest/1561/problem/D1
// Memory Limit: 128 MB
// Time Limit: 6000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e6 + 7;
#define ll long long
int rd() {
    int s = 0, f = 1; char c = getchar();
    while (c < ‘0‘ || c > ‘9‘) {if (c == ‘-‘) f = -1; c = getchar();}
    while (c >= ‘0‘ && c <= ‘9‘) {s = s * 10 + c - ‘0‘; c = getchar();}
    return s * f;
}
int n, m;
ll f[maxn], lst = 1;
ll sum[maxn];
int main() {
	n = rd(); m = rd();
	f[n] = 1;
	sum[n] = 1;
	for (int i = n - 1; i >= 1; i--) {
		f[i] = (f[i] + sum[i + 1]) % m;
		for (int x = 2; x * i <= n; x++) {
			f[i] = (f[i] + sum[x*i] - sum[min(x*i+x, n+1)] + m) % m;
		} 
		sum[i] = (sum[i+1]+f[i]) % m;
	}
	//for (int i = 1; i <= n; i++) printf("f[%d]==%d\n", i, f[i]);
	printf("%lld\n", f[1] % m);
	return 0;
}	

总结：dp和数论分块有时候可以倒过来思考，单源单汇的路径计数，也许可以交换源汇。

Codeforces Round #740 (Div. 2, based on VK Cup 2021 - Final (Engine)) (CF1561D1 & D2 Up the Strip)