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 ; 
}