Submission #3929327
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef signed long long ll; #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x<(to);x++) #define FORR(x,arr) for(auto& x:arr) #define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) //------------------------------------------------------- int N; int P[2020],NC[2020]; vector<int> E[2020]; int C[2020]; ll dp[2020][2020][3]; ll mo=1000000007; ll fact[2020]; ll dp2[2020][3]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; for(i=1;i<N;i++) { cin>>P[i]; P[i]--; E[P[i]].push_back(i); } fact[0]=1; FOR(i,N) fact[i+1]=fact[i]*(i+1)%mo; for(i=N-1;i>=0;i--) { C[i]=1; dp[i][1][0]=1; FORR(e,E[i]) { for(x=1;x<=C[i];x++) for(y=1;y<=C[e];y++) { // not con (dp2[x+y][0]+=dp[i][x][0]*(dp[e][y][0]+2*dp[e][y][1]+2*dp[e][y][2]))%=mo; (dp2[x+y][1]+=dp[i][x][1]*(dp[e][y][0]+2*dp[e][y][1]+2*dp[e][y][2]))%=mo; (dp2[x+y][2]+=dp[i][x][2]*(dp[e][y][0]+2*dp[e][y][1]+2*dp[e][y][2]))%=mo; // con (dp2[x+y-1][1]+=dp[i][x][0]*(dp[e][y][0]+dp[e][y][1]))%=mo; (dp2[x+y-1][2]+=dp[i][x][1]*(dp[e][y][0]+dp[e][y][1]))%=mo; } C[i]+=C[e]; FOR(j,C[i]+2) FOR(x,3) dp[i][j][x]=dp2[j][x], dp2[j][x]=0; } } ll ret=0; for(i=1;i<=N;i++) { if((N-i)%2==0) ret+=(dp[0][i][0]+2*dp[0][i][1]+2*dp[0][i][2])*fact[i]%mo; else ret-=(dp[0][i][0]+2*dp[0][i][1]+2*dp[0][i][2])*fact[i]%mo; } cout<<(ret%mo+mo)%mo<<endl; } int main(int argc,char** argv){ string s;int i; if(argc==1) ios::sync_with_stdio(false), cin.tie(0); FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin); cout.tie(0); solve(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Awkward |
User | kmjp |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 1893 Byte |
Status | AC |
Exec Time | 134 ms |
Memory | 94592 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 | 127 ms | 92800 KB |
b07 | AC | 134 ms | 94592 KB |
b08 | AC | 124 ms | 93056 KB |
b09 | AC | 124 ms | 92928 KB |
b10 | AC | 124 ms | 92928 KB |
b11 | AC | 124 ms | 92928 KB |
b12 | AC | 124 ms | 92800 KB |
b13 | AC | 125 ms | 92800 KB |
b14 | AC | 127 ms | 92800 KB |
b15 | AC | 124 ms | 93056 KB |
b16 | AC | 37 ms | 47744 KB |
b17 | AC | 2 ms | 4608 KB |
b18 | AC | 1 ms | 384 KB |
b19 | AC | 124 ms | 93056 KB |
b20 | AC | 124 ms | 92928 KB |
b21 | AC | 124 ms | 92928 KB |
b22 | AC | 124 ms | 93056 KB |
b23 | AC | 123 ms | 92928 KB |
b24 | AC | 124 ms | 92928 KB |
b25 | AC | 125 ms | 94592 KB |
b26 | AC | 127 ms | 92800 KB |
b27 | AC | 128 ms | 94592 KB |
b28 | AC | 127 ms | 92800 KB |
b29 | AC | 131 ms | 94592 KB |
b30 | AC | 132 ms | 94592 KB |
b31 | AC | 129 ms | 94592 KB |
b32 | AC | 134 ms | 94592 KB |
b33 | AC | 124 ms | 93056 KB |
b34 | AC | 124 ms | 93056 KB |
b35 | AC | 124 ms | 93184 KB |
b36 | AC | 124 ms | 92928 KB |
b37 | AC | 124 ms | 92928 KB |
b38 | AC | 124 ms | 93056 KB |
b39 | AC | 124 ms | 93056 KB |
b40 | AC | 124 ms | 93056 KB |
b41 | AC | 124 ms | 93056 KB |
b42 | AC | 124 ms | 92928 KB |
b43 | AC | 124 ms | 92928 KB |
b44 | AC | 124 ms | 93056 KB |
b45 | AC | 133 ms | 94464 KB |
b46 | AC | 134 ms | 94592 KB |
b47 | AC | 134 ms | 94592 KB |
b48 | AC | 134 ms | 94592 KB |
b49 | AC | 134 ms | 94592 KB |
b50 | AC | 127 ms | 92800 KB |
b51 | AC | 127 ms | 92800 KB |
b52 | AC | 127 ms | 92800 KB |
b53 | AC | 127 ms | 92800 KB |
b54 | AC | 127 ms | 92800 KB |
b55 | AC | 129 ms | 93696 KB |