题目分析
考虑 DP。
显然当没有 \(i\) 连向 \(i+1\) 的边时，整个图是一个 DAG，可以直接 DP。所以我们 DP 要解决的唯一问题，就是考虑上 \(i\) 到 \(i+1\) 的边。
考虑从 \(n\) 走到 \(1\) 的过程。当我们从 \(i\) 向前跳到 \(j\) 后，此时我们要么向前跳，要么往回走。又因为不能经过重复点，所以往回走最多只能走到 \(j-1\)。容易发现当到达 \(i\) 点时，这个位置的状态只有当前点 \(i\) 和跳过来的点 \(j\) 两维，我们可以以此设计 DP。
我们从 \(1\) 向 \(n\) 来 DP。\(f_{i,j}\) 代表当前从 \(j\) 向前 跳到点 \(i\) 后，到 \(1\) 的路径数目。此时可以向前跳到点 \(i-1\) 或 \(i\) 的因数。可以直接转移。（注意到此时限制已经从 \(j\) 变成了 \(i\)）
\[f_{i,j} = f_{i-1,i} + \sum_{y|i}f_{y,i} \]接下来就是往回走。状态为 \(f_{i,j}\) 时，可以往回走到 \(i+1\) 到 \(j-1\) 之间的任意地方再向前跳。
\[f_{i,j} = f_{i,j} + \sum_{x=i-1}^{j+1}\sum_{(y|x) \land (y<i)}f_{y,i} \]由于 \(y<i\) 这个限制不是很好处理，但因为我们是从 \(1\) 向 \(n\) DP，所以只需要每计算完一个 \(f\) 值就把它加到它的所有倍数上即可，将其记为 \(s_{i,j}\) ，那原式变为：
\[f_{i,j} = f_{i,j} + \sum_{x=i-1}^{j+1}s_{y,i} \]注意到这是一个区间查询，可以使用树状数组查询，复杂度 \(O(n^2 \log^2n)\)。（因为向因数连边，边数是 \(\log n\) 级别的）
for(int i=2;i<=n+1;i++)f[1][i]=1;xiangyinshulianbian
for(int x:son[1])
for(int j=2;j<=n+1;j++)
Add(x,f[1][j],j);
for(int i=2;i<=n;i++){
int bas=0;
for(int x:fa[i]){(bas+=f[x][i])%=p;}
(bas+=f[i-1][i])%=p;
for(int j=i+1;j<=n+1;j++){
(f[i][j]+=bas)%=p;
(f[i][j]+=(Query(j-1,i)-Query(i,i)+p)%p)%=p;
}
for(int x:son[i])
for(int j=i+1;j<=n+1;j++)
Add(x,f[i][j],j);
}
printf("%d\n",f[n][n+1]);
（其中 \(son\) 是倍数，\(fa\) 是因数）
但是她 T 了，所以要优化复杂度。
观察查询的过程，发现我们完全不需要树状数组，因为移动 \(j\) 时，\(f_{i,j}\) 只会改变一个数，一边求前缀和，一边改即可。时间复杂度 \(O(n^2 \log n)\)。
代码
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j+=i)
son[i].push_back(j),
fa[j].push_back(i);
for(int i=2;i<=n+1;i++)f[1][i]=1;
for(int x=2;x<=n;x++)
for(int j=2;j<=n+1;j++)s[x][j]=1;
for(int i=2;i<=n;i++){
long long bas=0;
for(int x:fa[i])bas+=f[x][i];
(bas+=f[i-1][i])%=p;
long long now=0;
for(int j=i+1;j<=n+1;j++){
f[i][j]+=bas+now;
now+=(s[j][i]%=p);
}
for(int j=i+1;j<=n+1;j++)f[i][j]%=p;
for(int x:son[i]){
for(int j=i+1;j<=n+1;j++)s[x][j]+=f[i][j];
}
}
printf("%d\n",f[n][n+1]);