Submission #2299347

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;
const int inv2 = 5e8 + 4;

vector< int > g[100000];
vector< vector< int64 > > dp[100000];

void rec(int idx) {
  vector< vector< int64 > > sub(3, vector< int64 >(1));
  sub[0][0] = 1;
  for(auto &to : g[idx]) {
    rec(to);
    auto &ch = dp[to];
    vector< int64 > sub1(ch[0].size() + 1);
    for(int i = 0; i < ch[0].size(); i++) {
      (sub1[i + 1] += ch[0][i] * 2) %= mod;
      (sub1[i + 1] += ch[1][i]) %= mod;
    }

    vector< vector< int64 > > beet(3, vector< int64 >(sub[0].size() + ch[0].size()));
    for(int k = 0; k < 3; k++) {
      for(int i = 0; i < sub[k].size(); i++) {
        for(int j = 0; j <= ch[0].size(); j++) {
          if(j < ch[0].size()) {
            for(int l = 0; l < 3; l++) {
              (beet[k][i + j] += sub[k][i] * ch[l][j] % mod) %= mod;
            }
          }
          if(k == 0) (beet[1][i + j] += sub[k][i] * sub1[j]) %= mod;
          if(k == 1) (beet[2][i + j] += sub[k][i] * sub1[j] % mod * inv2) %= mod;
        }
      }
    }

    sub.swap(beet);
  }
  dp[idx].swap(sub);
}

int main() {
  int N;
  cin >> N;
  for(int i = 1; i < N; i++) {
    int p;
    cin >> p;
    g[--p].emplace_back(i);
  }

  int64 fact[2002];
  fact[0] = 1;
  for(int i = 1; i < 2002; i++) {
    (fact[i] = fact[i - 1] * i) %= mod;
  }

  rec(0);

  int64 ret = 0;
  for(int i = 0; i < N; i++) {
    int64 add = 0;
    for(int j = 0; j < 3; j++) (add += dp[0][j][i]) %= mod;
    (add *= fact[N - i]) %= mod;
    if(i & 1) (ret += mod - add) %= mod;
    else (ret += add) %= mod;
  }

  cout << ret << endl;
}

Submission Info

Judge Result