从点 $n$ 开始，只有两种跳法：跳到 $n-1$ 处，或者跳到 $n$ 的因子 $d$ 处. 跳到 $n-1$ 处后等同于从 $n-1$ 处开始，但跳到 $d$ 和从 $d$ 开始有一定区别，因为跳完后还可以往前跳（只要不超过 $n-1$ 即可）.

(上图黑线表示第一步、蓝线表示第二步，直线表示从 $i$ 跳到 $i\pm1$ 的类型，曲线从 $i$ 跳到 $i$ 的因子的类型.)

我们用 $f_{i,j}$ 表示从 $i$ 出发到 $1$，且经过的点在 $[1,j]$ 范围内的方案数，我们要求的答案即为 $f_{n,n}$. 根据前面的分析，可以得到:

那么对于 $j>i$ 的 $f_{i,j}$ 怎么求呢？首先根据定义 $f_{i,j-1}$ 的方案对 $f_{i,j}$ 有贡献.

如果我们要到达 $j$ 点，必须是刚开始就从 $i$ 向前跳到 $j$，到达 $j$ 点后，不能再到 $j-1$ 或者 $j+1$，只能跳到 $j$ 的因子处离开，且这个因子必须小于 $i$.

可以得到：

观察到我们推的两个式子形式相似，可以放在一个循环中，动态规划的边界即为 $f_{1,i} = 1$.

对于每个数，我们可以提前预处理因子，算法的时间复杂度为 $n\sqrt n+n^2\cdot d(n)$，优化一下常数，把对 $k$ 取模改成减去 $k$ 即可通过.

代码：

#include <iostream>
#include <vector>
const int MAXN = 5005;
using namespace std;
int n;
long long f[MAXN][MAXN], mod;
vector<int> d[MAXN];
int main() {
    cin >> n >> mod;
    for (int i = 1; i <= n; ++i) f[1][i] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j * j <= i; ++j) {
            if (i % j == 0) {
                d[i].push_back(j);
                if (i / j != j) d[i].push_back(i / j);
            }
        }
    }
    for (int i = 2; i <= n; ++i) {
        f[i][i] = f[i - 1][i - 1];
        for (int j = i; j <= n; ++j) {
            f[i][j] += f[i][j - 1];
            for (int k : d[j]) {
                if (k < i) {
                    f[i][j] += f[k][i - 1];
                    if (f[i][j] > mod) f[i][j] -= mod;
                }
            }
        }
    }
    cout << f[n][n] % mod << endl;
    return 0;
}

666 这场比赛怎么全是 DP。

题意

连续 $n$ 个下标 $1,2,3,...,n$，最开始你在下标 $n$，每次可以从 $i$ 走到 $i-1$ 和 $i+1$，或者走到 $i$ 的约数下标（这是两种不同的走法），每个下标只能走一次，问你有多少种从 $n$ 走到 $1$的走法（不能走出 $1$ 到 $n$ 的范围）。

思考过程

如果只有向一边走的情况，那么这个题很容易做，但是这里多出来一种向回走的情况，这就不太好考虑了。

但是我们可以发现，向回走一定是只能一格一格的走，并且一定存在于原来某次跳约数的中间未被访问的部分。

比如下图中从 $8$ 跳到 $2$（跳约数），这样的话，$3$ 到 $7$ 的下标都没有被跳过，因此完全可以考虑这个时候从 $2$ 往回一格一格跳，比如考虑跳到 $5$，那么此时所有能够跳到 $8$ 的方案，通过 $2$ 一定能够跳到 $5$，所以此时可以让 $5$ 累加上跳到 $8$ 的方案，注意不是加 $2$ 的，$2$ 中包含有其他的方案，与我们现在讨论的不一致。

但是直接加上 $8$ 的就好了吗？实际上还存在一类问题。

绿色和红色是曾今走到 $8$ 的一种决策，这一决策经过了 $5$，而如今我们在对 $5$ 进行决策时，却没有考虑到 $5$ 已经被先前的某些方案所覆盖（已经被走过了），所以我们必须记录一下，点 $i$ 是从前面哪个点往后走到的，比如这里 $8$ 是从 $5$ 走到的，所以后来我们在考虑蓝色路径时（对 $5$ 的决策），只能让 $5$ 累加上从 $6,7$ 走到 $8$（这个东西就是个后缀和嘛），或者从 $8$ 后面来到 $8$ 的情况的方案数。

所以接下来思路就很明确了：

定义状态 $f_{i,j}$ 表示从 $j,j+1,j+2,...,i$ 向后走走到的 $i$ 的方案数，这里我为了好统计，将 $f_{i,i}$ 的状态特殊定义为从 $i$ 后面走到 $i$ 的方案数。

对于向前一格的情况：$f_{i,i}=f_{i,i}+f_{i+1,i+1}$

对于从 $l$ 跳约数来到 $i$ 的情况：$f_{i,i}=f_{i,i}+f_{l,i+1}$（$i$ 是 $l$ 的约数）

接下来着重看一下往回跳的情况

下面是 $i=2$ 的情况，我们考虑 $j$ 通过约数的跳法来到 $i$，此时我们在 $i+1$ 到 $j-1$ 中枚举 $k$，此时将 $k$ 累加上 $j$ 从 $k+1,k+2,k+3,...,j$ 跳过来的方案数：对于 $i+1\le k\le j-1$ 有 $f_{k,i}=f_{k,i}+f_{j,k+1}$（从后面来到 $j$ 的方案数根据定义统计在 $f_{j,j}$ 中，被正常累计在 $k$ 上）。

我们是在对第 $f_{j,i}$ 中的第二维进行后缀和，第二维就是下图中的 $i$（对于每次枚举的 $i$，只需要修改 $f_{i,i}$ 和 $f_{k,i}$），所以对于每个 $i$ 计算完后，再刷一遍 $i$ 的后缀和就好了。具体的，每次关于 $i$ 的计算结束后，枚举 $1\le k\le n$，令 $f_{k,i}=f_{k,i}+f_{k,i+1}$

时间复杂度

第一层循环一个 $i$，第二层循环 $i$ 的倍数 $j$（不包括 $i$），第三层循环 $i$ 到 $j$ 的所有数

第一层可以看成 $\frac{n}{2}$，因为再往上就不会有 $i$ 的倍数了（因为倍数都超过 $n$ ）。

接下来第二层和第三层是一个等差数列求和，公差为 $i$。对于一个 $i$，需要计算 $[i,2\times i],[i,3\times i],[i,4\times i],...,[i,n]$ 这些区间（每个区间长度比前一个多 $i$，共有 $\frac{n-i}{i}$ 个区间），计算次数就是 $(2\times i-i)+(3\times i-i)+(4\times i-i)+...+(n-i)$，这里直接把 $n-i$ 看成 $n$ 就好。

$i+2\times i+3\times i+...+n=\frac{n-i}{i}\times \frac{(n+i)}{2}$，$\frac{n-i}{i}$ 是项数。

把 $n-i$ 估大成 $n$，把 $n+i$ 估大成 $2\times n$。

得到 $\frac{n}{i}\times\frac{2\times n}{2}=\frac{2\times n^2}{2\times i}=\frac{n^2}{i}$，再把 $i$ 带入得到 $\displaystyle\sum_{i=1}^{\frac{n}{2}}\frac{n^2}{i}=n\times \displaystyle\sum_{i=1}^{\frac{n}{2}} \frac{n}{i}=n^2\times\ln(n)$，ok拿下。

#include<bits/stdc++.h>
using namespace std ;
const int Max = 5e3 + 10 ; 
vector < int > Start[Max] , Prinm[Max] ; 
int g[Max][Max] ; 
int f[Max][Max] ;
int n , p ;
int main( ) {
	scanf("%d%d" , &n , &p ) ; 
	// 边界情况特殊处理 
	f[n + 1][n + 1] = 1 ; 
	for(int i = n ; i >= 1 ; i -- ) {
		// i 从 i+1 走来
		// 所以对 f[i][i] 修改即可 
		f[i][i] = ( f[i][i] + f[i + 1][i + 1] ) % p ;  
		
		for(int l = 2 * i ; l <= n ; l += i ) {
			// i 从 l 跳来，这里注意只有 l 是从 i+1,i+2,...,l 跳过来的方案需要被累计 
			f[i][i] = ( f[i][i] + f[l][i + 1] ) % p ; 
			
			for(int k = i + 1 ; k <= l - 1 ; k ++ ) {
				// l 从 k+1,k+2,...,l 跳过来
				// k 从 i 跳过来 
				f[k][i] = ( f[k][i] + f[l][k + 1] ) % p ; 
				
			}
		}
		// 每次 i 计算完，救刷新一下后缀和 
		for(int l = 1 ; l <= n ; l ++ ) f[l][i] = ( f[l][i] + f[l][i + 1] ) % p ; 
	}
	// 答案就是从 1 后面跳过来 
	printf("%d\n" , f[1][1] ) ;
	return false ; 
}