Submission #1883114

---

Source Code Expand

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

ll dp[2010][2];
ll nb_depth[2010];

vector<int> G[2010];
const ll MOD = 1e9+7;
 
void count_depth(int v, int depth){
	nb_depth[depth]++;
	REP(i, G[v].size()){
		count_depth(G[v][i], depth+1);
	}
}


ll mpow(ll a, ll b){
	if(b == 0) return 1;
	if(b < 0) return 0;
	if(b%2) return (a*mpow(a, b-1)) % MOD;
	ll ret = mpow(a, b/2);
	return (ret*ret)%MOD;
}

void dfs(int v, int d) {
    if(d == 0) {
        dp[v][0] = dp[v][1] = 1;
        return;
    }
    ll x = 1, y = 1;
    for(auto c: G[v]) {
        dfs(c, d-1);
        x = (x * dp[c][0]) % MOD;
        y = (y * (dp[c][0]+dp[c][1])) % MOD;
    }
    for(auto c: G[v]) {
        // n^{-1} mod p = n^{p-2} mod p
        dp[v][1] += ((x * mpow(dp[c][0], MOD-2)) % MOD * dp[c][1]) % MOD;
        dp[v][1] %= MOD;
    }
    dp[v][0] = (y - dp[v][1] + MOD) % MOD;
}


int main(void) {
    int N;
    cin >> N;
    if(N>2000) return 0;
    REP(i, N) {
        int p;
        cin >> p;
        G[p].push_back(i+1);
    }
    count_depth(0, 0);
    ll ans = 0;
    REP(d, N+1) {
        REP(j, 2010) {
            REP(k, 2) {
                dp[j][k] = 0;
            }
        }
        dfs(0, d);
        ans = (ans + dp[0][1] * mpow(2, N-nb_depth[d]+1)) % MOD;
    }
    cout << ans << endl;
}

Submission Info

Judge Result