Submission #3831783
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long lint; typedef pair<int, int> pi; const int MAXN = 2005; const int mod = 1e9 + 7; int n, sz[MAXN], p[MAXN]; vector<int> gph[MAXN]; lint dp[MAXN][MAXN][2]; lint fact[MAXN]; lint aux[MAXN][3], nxt[MAXN][3]; int main(){ fact[0] = 1; for(int i=1; i<MAXN; i++) fact[i] = fact[i-1] * i % mod; cin >> n; for(int i=2; i<=n; i++){ cin >> p[i]; gph[p[i]].push_back(i); } for(int i=n; i; i--){ memset(aux, 0, sizeof(aux)); aux[0][0] = 1; for(auto &j : gph[i]){ memset(nxt, 0, sizeof(nxt)); for(int k=0; k<=sz[j]; k++){ for(int l=0; l<=sz[i]; l++){ for(int m=0; m<3; m++){ nxt[k + l][m] += dp[j][k][0] * aux[l][m] % mod; if(m < 2) nxt[k + l + 1][m+1] += dp[j][k][1] * aux[l][m] % mod; } } } sz[i] += sz[j]; memcpy(aux, nxt, sizeof(aux)); } for(int j=0; j<=sz[i]; j++){ dp[i][j][0] = aux[j][0] + aux[j][1] * 2 + aux[j][2] * 2; dp[i][j][1] = aux[j][0] + aux[j][1]; dp[i][j][0] %= mod; dp[i][j][1] %= mod; } sz[i]++; } lint ret = 0; for(int i=0; i<=n; i++){ lint cur = dp[1][i][0] * fact[n - i] % mod; if(i & 1) cur = mod - cur; ret += cur; } cout << ret % mod << endl; }
Submission Info
Submission Time | |
---|---|
Task | A - Awkward |
User | koosaga |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1269 Byte |
Status | WA |
Exec Time | 61 ms |
Memory | 61952 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 1000 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | a01, a02, a03, a04 |
All | a01, a02, a03, a04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, b25, b26, b27, b28, b29, b30, b31, b32, b33, b34, b35, b36, b37, b38, b39, b40, b41, b42, b43, b44, b45, b46, b47, b48, b49, b50, b51, b52, b53, b54, b55 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
a01 | AC | 2 ms | 384 KB |
a02 | AC | 2 ms | 384 KB |
a03 | AC | 2 ms | 384 KB |
a04 | AC | 2 ms | 512 KB |
b05 | AC | 2 ms | 384 KB |
b06 | AC | 60 ms | 60288 KB |
b07 | AC | 55 ms | 61952 KB |
b08 | AC | 43 ms | 60416 KB |
b09 | WA | 43 ms | 60416 KB |
b10 | WA | 43 ms | 60416 KB |
b11 | WA | 44 ms | 60288 KB |
b12 | AC | 44 ms | 60288 KB |
b13 | AC | 48 ms | 60288 KB |
b14 | AC | 60 ms | 60288 KB |
b15 | AC | 44 ms | 60416 KB |
b16 | WA | 18 ms | 31488 KB |
b17 | AC | 3 ms | 2688 KB |
b18 | AC | 2 ms | 512 KB |
b19 | WA | 43 ms | 60416 KB |
b20 | WA | 43 ms | 60416 KB |
b21 | WA | 43 ms | 60288 KB |
b22 | WA | 43 ms | 60416 KB |
b23 | WA | 45 ms | 60288 KB |
b24 | WA | 44 ms | 60416 KB |
b25 | AC | 45 ms | 61952 KB |
b26 | AC | 61 ms | 60288 KB |
b27 | WA | 48 ms | 61952 KB |
b28 | AC | 60 ms | 60288 KB |
b29 | AC | 53 ms | 61952 KB |
b30 | WA | 53 ms | 61952 KB |
b31 | WA | 50 ms | 61952 KB |
b32 | AC | 55 ms | 61952 KB |
b33 | AC | 44 ms | 60544 KB |
b34 | WA | 44 ms | 60416 KB |
b35 | AC | 44 ms | 60544 KB |
b36 | WA | 44 ms | 60416 KB |
b37 | WA | 44 ms | 60416 KB |
b38 | AC | 44 ms | 60416 KB |
b39 | WA | 44 ms | 60416 KB |
b40 | WA | 44 ms | 60416 KB |
b41 | WA | 44 ms | 60416 KB |
b42 | WA | 44 ms | 60416 KB |
b43 | WA | 44 ms | 60416 KB |
b44 | WA | 44 ms | 60416 KB |
b45 | AC | 54 ms | 61824 KB |
b46 | AC | 55 ms | 61824 KB |
b47 | AC | 55 ms | 61952 KB |
b48 | AC | 55 ms | 61952 KB |
b49 | AC | 55 ms | 61952 KB |
b50 | AC | 60 ms | 60288 KB |
b51 | AC | 60 ms | 60288 KB |
b52 | AC | 60 ms | 60288 KB |
b53 | AC | 61 ms | 60288 KB |
b54 | AC | 61 ms | 60288 KB |
b55 | AC | 49 ms | 61184 KB |