CF407B Long Path

好玩的题。

首先我们（看一下题解之后）发现当你第一次走到了一个点的时候，那么它之前的所有点一定都访问过了偶数次。

假设我们第一次走到了一个点$i$，那么$i - 1$一定访问了偶数次，那么第一次走$i - 1$的时候会走到$p_{i - 1}$，也就是说不断重复这个走偶数次的过程最终到达了$i$。

因为题目保证了$p_i leq i$，所以我们可以$dp$了，设$f_{i, j}$表示从$i$走到$j$需要的步数。

边界：$f_{i, i} = 1$。注意这里是从$i$走到$i$，而不是停在原地不动了。

有方程：$f_{i, j} = f_{i, j - 1} + f_{p_{j - 1}, j - 1} + 1$。

解释一下：要从$i$走到$j$，需要先走到$j - 1$，然后从$p_{j - 1}$走回到$j - 1$，再走一步走到$j$。

最后答案是$f_{1, n + 1} - 1$，因为一开始就在$1$。

然而转移顺序似乎并不明显，记忆化搜索实现。

时间复杂度$O(n^2)$。

Code：

#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1005;
const int P = 1e9 + 7;

int n, nxt[N], f[N][N];

inline void read(int &X) {
    X = 0; char ch = 0; int op = 1;
    for(; ch > '9' || ch < '0'; ch = getchar())
        if(ch == '-') op = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
}

inline void inc(int &x, int y) {
    x += y;
    if(x >= P) x -= P;
}

inline void sub(int &x, int y) {
    x -= y;
    if(x < 0) x += P;
}

int dfs(int i, int j) {
    if(i == j) return f[i][j] = 1;
    if(f[i][j]) return f[i][j];
    int res = 0;
    inc(res, dfs(i, j - 1));
    inc(res, dfs(nxt[j - 1], j - 1));
    inc(res, 1);
    return f[i][j] = res;
}

int main() {
    read(n);
    for(int i = 1; i <= n; i++) read(nxt[i]);
    int ans = dfs(1, n + 1);
    sub(ans, 1);
    printf("%d
", ans);
    return 0;
}