Submission #1815583
Source Code Expand
#include<iostream> #include<vector> #include<algorithm> #include<cstring> #include<cstdio> #include<cmath> #include<cstdlib> #include<ctime> #include<queue> #include<set> #include<map> #include<stack> #include<bitset> #define pb push_back #define mp make_pair using namespace std; template<typename T>inline void upmin(T &x,T y) { y<x?x=y:0; } template<typename T>inline void upmax(T &x,T y) { x<y?x=y:0; } typedef unsigned int u32; typedef long long LL; typedef unsigned long long ULL; typedef long double lod; typedef pair<int,int> PR; typedef vector<int> VI; const lod pi=acos(-1); const int oo=1<<30; const LL OO=1e18; const int N=2010; int gi() { int w=0;bool q=1;char c=getchar(); while ((c<'0'||c>'9') && c!='-') c=getchar(); if (c=='-') q=0,c=getchar(); while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar(); return q? w:-w; } int siz[N],fa[N]; int f0[N][N],f1[N][N],f2[N][N]; int F0[N],F1[N],F2[N]; int main() { int n=gi(),i,j,k,t,ans=0,s,fac; const int mod=1e9+7,inv2=(mod+1)>>1; for (i=2;i<=n;i++) fa[i]=gi(); for (i=1;i<=n;i++) siz[i]=1,f0[i][1]=1; for (k=n;k>1;k--) { t=fa[k]; for (i=0;i<=siz[k]+siz[t];i++) F0[i]=F1[i]=F2[i]=0; for (i=1;i<=siz[t];i++) for (j=1;j<=siz[k];j++) { s=((LL)f0[k][j]+f1[k][j]+f2[k][j])%mod; F2[i+j]=(F2[i+j]+1LL*f2[t][i]*s)%mod; F2[i+j-1]=(F2[i+j-1]+1LL*f1[t][i]*f1[k][j]%mod*inv2+1LL*f1[t][i]*f0[k][j])%mod; F1[i+j]=(F1[i+j]+1LL*f1[t][i]*s)%mod; F1[i+j-1]=(F1[i+j-1]+1LL*f0[t][i]*(f1[k][j]+2LL*f0[k][j]))%mod; F0[i+j]=(F0[i+j]+1LL*f0[t][i]*s)%mod; } for (i=siz[t]+=siz[k];~i;i--) f0[t][i]=F0[i],f1[t][i]=F1[i],f2[t][i]=F2[i]; } for (i=fac=1;i<=n;i++) { fac=1LL*fac*i%mod; ans=(ans+((n^i)&1?-1:1)*fac*((LL)f0[1][i]+f1[1][i]+f2[1][i]))%mod; } cout<<(ans+mod)%mod<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Awkward |
User | laofu |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 1866 Byte |
Status | AC |
Exec Time | 48 ms |
Memory | 47488 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 | 2 ms | 4352 KB |
a02 | AC | 2 ms | 4352 KB |
a03 | AC | 2 ms | 4352 KB |
a04 | AC | 2 ms | 4352 KB |
b05 | AC | 2 ms | 4352 KB |
b06 | AC | 39 ms | 18816 KB |
b07 | AC | 47 ms | 47488 KB |
b08 | AC | 35 ms | 34176 KB |
b09 | AC | 34 ms | 30080 KB |
b10 | AC | 33 ms | 25984 KB |
b11 | AC | 32 ms | 21632 KB |
b12 | AC | 31 ms | 19072 KB |
b13 | AC | 32 ms | 18816 KB |
b14 | AC | 35 ms | 18816 KB |
b15 | AC | 35 ms | 34176 KB |
b16 | AC | 11 ms | 15360 KB |
b17 | AC | 2 ms | 4352 KB |
b18 | AC | 2 ms | 4352 KB |
b19 | AC | 35 ms | 34176 KB |
b20 | AC | 34 ms | 30080 KB |
b21 | AC | 33 ms | 25984 KB |
b22 | AC | 35 ms | 34048 KB |
b23 | AC | 34 ms | 30080 KB |
b24 | AC | 33 ms | 25984 KB |
b25 | AC | 34 ms | 26368 KB |
b26 | AC | 40 ms | 18816 KB |
b27 | AC | 37 ms | 31104 KB |
b28 | AC | 38 ms | 19072 KB |
b29 | AC | 45 ms | 43392 KB |
b30 | AC | 44 ms | 43392 KB |
b31 | AC | 42 ms | 43392 KB |
b32 | AC | 47 ms | 47488 KB |
b33 | AC | 38 ms | 46464 KB |
b34 | AC | 39 ms | 46592 KB |
b35 | AC | 39 ms | 46592 KB |
b36 | AC | 38 ms | 46464 KB |
b37 | AC | 38 ms | 46464 KB |
b38 | AC | 38 ms | 46464 KB |
b39 | AC | 38 ms | 46592 KB |
b40 | AC | 38 ms | 46464 KB |
b41 | AC | 38 ms | 46464 KB |
b42 | AC | 38 ms | 46464 KB |
b43 | AC | 38 ms | 46464 KB |
b44 | AC | 38 ms | 46464 KB |
b45 | AC | 47 ms | 47360 KB |
b46 | AC | 47 ms | 47360 KB |
b47 | AC | 47 ms | 47488 KB |
b48 | AC | 47 ms | 47488 KB |
b49 | AC | 48 ms | 47488 KB |
b50 | AC | 42 ms | 33408 KB |
b51 | AC | 42 ms | 33280 KB |
b52 | AC | 42 ms | 31104 KB |
b53 | AC | 43 ms | 31104 KB |
b54 | AC | 41 ms | 22912 KB |
b55 | AC | 47 ms | 46848 KB |