题解 | #附加题#

这种题目首先肯定是找模型

我先想到的肯定是如果 pi 都为 1 ，要怎么处理 
然后发现这个简单了 如果到底n个房间的次数为 P（n）；

P（n + 1） = 2 * P（n） + 2 ；//因为回到1 肯定就是重走一遍 1 到 n 的路程  所以肯定是2倍了 然后有 额外走了 回 1 和到 n + 1 的路程 所以要 + 2

这个时候我们可以开始想  如果 不是会第一个位置 怎么减？
假定  到第 n 个位置 需要 P(n) 次 ，n 处的 指向房间 pi 为 x
不难推出 我们只是跳过了上面从 房间 1 到 房间 x 的过程，所以如下即可
P(n + 1) = 2* P(n) + 2 - P(x)
如此 把 n 个房间的 指向房间 给成数组形式即可  arr[n -1] 就是第n 间房的 指向数 Pi  即 x
P(n+1) = 2 * P(n) + 2 - P(arr[n-1])
将 n + 1 换成 n ，则  P(n) = 2 * P(n-1) + 2 - P（arr[n-2]）

可得函数，
function getNumAll(n,arr){
        if(n == 1){
        return 0
    }else if(n == 2){
        return 2;
    }else{  return 2*getNumAll(n-1,arr) + 2 - getNumAll(parseInt(arr[n-2]),arr);
        }
}
又因为需要取模 1000000007 

所以返回值 取模 即可

但是测试发现有误，猜测是数值过大，然后 返回值提前判断 是否需要取模，再测试，发现取值负数了，所以又加了一次
虽然成功了，但是一看速度。。。汗



Ps:提交代码如下

var n = parseInt(readline());
var arr = readline().split(" ");
print(getNumAll(1*n+1,arr)%1000000007);
function getNumAll(n,arr){
    if(n == 1){
        return 0
    }else if(n == 2){
		return 2;
	}else{
        var result = 2*getNumAll(n-1,arr) + 2 - getNumAll(parseInt(arr[n-2]),arr);
        if(result > 1000000007){
            result = result % 1000000007;
        }
        
		return result + 1000000007;
	}
}