Submission #2162136
Source Code Expand
#include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <cstring> #include <vector> #include <queue> #include <set> #include <map> #include <cmath> #include <iomanip> #include <cassert> #include <bitset> using namespace std; typedef pair<int, int> P; #define rep(i, n) for (int i=0; i<(n); i++) #define all(c) (c).begin(), (c).end() #define uniq(c) c.erase(unique(all(c)), (c).end()) #define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin()) #define _1 first #define _2 second #define pb push_back #define INF 1145141919 #define MOD 1000000007 int N; vector<int> G[2000]; int B[2000]; int fact[2001]; vector<int> dp[2000][2]; vector<int> dp2[2][3]; vector<int> merge(vector<int> &a, vector<int> &b) { vector<int> o(a.size()+b.size()-1, 0); rep(i, a.size()) { rep(j, b.size()) { o[i+j] = (o[i+j] + 1LL*a[i]*b[j])%MOD; } } return o; } void add(vector<int> &to, vector<int> src) { if (to.size() < src.size()) to.resize(src.size(), 0); rep(i, src.size()) to[i] = (to[i]+src[i]) % MOD; } signed main() { ios::sync_with_stdio(false); cin.tie(0); fact[0] = 1; for (int i=1; i<=2000; i++) fact[i] = (1LL*i*fact[i-1])%MOD; cin >> N; for (int i=1; i<N; i++) { int p; cin >> p; p--; G[p].pb(i); } for (int x=N-1; x>=0; x--) { dp2[0][0] = {1}; dp2[0][1] = {0}; dp2[0][2] = {0}; for (int t : G[x]) { rep(k, 3) dp2[1][k].clear(); rep(k, 3) add(dp2[1][k], merge(dp2[0][k], dp[t][0])); rep(k, 2) add(dp2[1][k+1], merge(dp2[0][k], dp[t][1])); swap(dp2[0], dp2[1]); } add(dp[x][1], dp2[0][0]); add(dp[x][1], dp2[0][1]); dp[x][1].insert(dp[x][1].begin(), 0); // s++ add(dp[x][0], dp2[0][0]); for (int &x : dp2[0][1]) x = (2LL*x) % MOD; for (int &x : dp2[0][2]) x = (2LL*x) % MOD; add(dp[x][0], dp2[0][1]); add(dp[x][0], dp2[0][2]); } int sum = 0; for (int s=0; s<dp[0][0].size(); s++) { int e = dp[0][0][s]; if (s%2) e = (MOD-e) % MOD; sum = (sum + 1LL*e*fact[N-s])%MOD; } cout << sum << "\n"; return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Awkward |
User | funcsr |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 2174 Byte |
Status | AC |
Exec Time | 90 ms |
Memory | 32000 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1000 / 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 | 1 ms | 384 KB |
a02 | AC | 1 ms | 384 KB |
a03 | AC | 1 ms | 384 KB |
a04 | AC | 1 ms | 384 KB |
b05 | AC | 1 ms | 384 KB |
b06 | AC | 3 ms | 512 KB |
b07 | AC | 90 ms | 32000 KB |
b08 | AC | 12 ms | 768 KB |
b09 | AC | 8 ms | 640 KB |
b10 | AC | 6 ms | 640 KB |
b11 | AC | 4 ms | 640 KB |
b12 | AC | 3 ms | 512 KB |
b13 | AC | 3 ms | 512 KB |
b14 | AC | 3 ms | 512 KB |
b15 | AC | 12 ms | 768 KB |
b16 | AC | 3 ms | 512 KB |
b17 | AC | 1 ms | 384 KB |
b18 | AC | 1 ms | 384 KB |
b19 | AC | 12 ms | 768 KB |
b20 | AC | 8 ms | 640 KB |
b21 | AC | 6 ms | 640 KB |
b22 | AC | 11 ms | 768 KB |
b23 | AC | 10 ms | 640 KB |
b24 | AC | 7 ms | 640 KB |
b25 | AC | 8 ms | 1536 KB |
b26 | AC | 3 ms | 512 KB |
b27 | AC | 16 ms | 4864 KB |
b28 | AC | 8 ms | 512 KB |
b29 | AC | 56 ms | 19200 KB |
b30 | AC | 55 ms | 18944 KB |
b31 | AC | 39 ms | 12544 KB |
b32 | AC | 83 ms | 29312 KB |
b33 | AC | 16 ms | 896 KB |
b34 | AC | 26 ms | 2048 KB |
b35 | AC | 25 ms | 1792 KB |
b36 | AC | 14 ms | 768 KB |
b37 | AC | 13 ms | 768 KB |
b38 | AC | 16 ms | 896 KB |
b39 | AC | 16 ms | 896 KB |
b40 | AC | 14 ms | 768 KB |
b41 | AC | 14 ms | 768 KB |
b42 | AC | 14 ms | 768 KB |
b43 | AC | 13 ms | 768 KB |
b44 | AC | 14 ms | 768 KB |
b45 | AC | 77 ms | 27136 KB |
b46 | AC | 85 ms | 29952 KB |
b47 | AC | 89 ms | 31488 KB |
b48 | AC | 90 ms | 31488 KB |
b49 | AC | 90 ms | 32000 KB |
b50 | AC | 12 ms | 512 KB |
b51 | AC | 6 ms | 512 KB |
b52 | AC | 4 ms | 512 KB |
b53 | AC | 3 ms | 512 KB |
b54 | AC | 3 ms | 512 KB |
b55 | AC | 41 ms | 12544 KB |