Submission #2298879
Source Code Expand
#include<bits/stdc++.h> using namespace std; #define int long long #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() #define fi first #define se second typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} const int mod=1000000007; inline void add(int &a,int b){ a+=b; if(a>=mod)a-=mod; } int mpow(int n,int m){ int ret=1; while(m){ if(m&1)ret=ret*n%mod; n=n*n%mod; m>>=1; } return ret; } const int FACT_SIZE=1111111; int fact[FACT_SIZE]; int inv[FACT_SIZE]; struct fact_exec{ fact_exec(){ fact[0]=1; for(int i=1;i<FACT_SIZE;i++)fact[i]=fact[i-1]*i%mod; inv[FACT_SIZE-1]=mpow(fact[FACT_SIZE-1],mod-2); for(int i=FACT_SIZE-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod; } }factexec; int nCk(int n,int k){ return fact[n]*inv[k]%mod*inv[n-k]%mod; } int nPk(int n,int k){ return fact[n]*inv[n-k]%mod; } int inv2=(mod+1)/2; int N; vint G[2222]; int dp[2222][2222][3]; int sz[2222]; int tmp[2222][3]; void dfs(int v){ sz[v]=1; dp[v][1][0]=1; for(auto u:G[v]){ dfs(u); rep(i,sz[v]+sz[u]+1)rep(j,3)tmp[i][j]=0; for(int i=1;i<=sz[v];i++){ for(int j=1;j<=sz[u];j++){ //0 0 add(tmp[i+j][0],dp[v][i][0]*dp[u][j][0]%mod); add(tmp[i+j-1][1],dp[v][i][0]*dp[u][j][0]*2%mod); //0 1 add(tmp[i+j][0],dp[v][i][0]*dp[u][j][1]%mod); add(tmp[i+j-1][1],dp[v][i][0]*dp[u][j][1]%mod); //0 2 add(tmp[i+j][0],dp[v][i][0]*dp[u][j][2]%mod); //1 0 add(tmp[i+j][1],dp[v][i][1]*dp[u][j][0]%mod); add(tmp[i+j-1][2],dp[v][i][1]*dp[u][j][0]%mod); //1 1 add(tmp[i+j][1],dp[v][i][1]*dp[u][j][1]%mod); add(tmp[i+j-1][2],dp[v][i][1]*dp[u][j][1]%mod*inv2%mod); //1 2 add(tmp[i+j][1],dp[v][i][1]*dp[u][j][2]%mod); //2 0 add(tmp[i+j][2],dp[v][i][2]*dp[u][j][0]%mod); //2 1 add(tmp[i+j][2],dp[v][i][2]*dp[u][j][1]%mod); //2 2 add(tmp[i+j][2],dp[v][i][2]*dp[u][j][2]%mod); } } sz[v]+=sz[u]; rep(i,sz[v]+1)rep(j,3)dp[v][i][j]=tmp[i][j]; } } signed main(){ cin>>N; for(int i=1;i<N;i++){ int b;cin>>b; b--; G[b].pb(i); } dfs(0); int ans=0; for(int i=1;i<=N;i++){ int ei=0; rep(j,3)add(ei,dp[0][i][j]); ei=ei*fact[i]%mod; if((N-i)&1){ ans=(ans-ei+mod)%mod; } else{ ans=(ans+ei)%mod; } } cout<<ans<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Awkward |
User | latte0119 |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 3106 Byte |
Status | AC |
Exec Time | 157 ms |
Memory | 123520 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 | 17 ms | 18816 KB |
a02 | AC | 17 ms | 18816 KB |
a03 | AC | 17 ms | 18816 KB |
a04 | AC | 17 ms | 18816 KB |
b05 | AC | 17 ms | 18816 KB |
b06 | AC | 86 ms | 121472 KB |
b07 | AC | 102 ms | 123520 KB |
b08 | AC | 115 ms | 121600 KB |
b09 | AC | 103 ms | 121600 KB |
b10 | AC | 94 ms | 121600 KB |
b11 | AC | 82 ms | 121600 KB |
b12 | AC | 78 ms | 121472 KB |
b13 | AC | 80 ms | 121472 KB |
b14 | AC | 86 ms | 121472 KB |
b15 | AC | 114 ms | 121600 KB |
b16 | AC | 39 ms | 70272 KB |
b17 | AC | 18 ms | 23040 KB |
b18 | AC | 16 ms | 18816 KB |
b19 | AC | 120 ms | 121728 KB |
b20 | AC | 103 ms | 121600 KB |
b21 | AC | 95 ms | 121600 KB |
b22 | AC | 114 ms | 121728 KB |
b23 | AC | 105 ms | 121472 KB |
b24 | AC | 93 ms | 121600 KB |
b25 | AC | 88 ms | 123136 KB |
b26 | AC | 86 ms | 121472 KB |
b27 | AC | 90 ms | 123264 KB |
b28 | AC | 88 ms | 121472 KB |
b29 | AC | 103 ms | 123392 KB |
b30 | AC | 103 ms | 123392 KB |
b31 | AC | 104 ms | 123264 KB |
b32 | AC | 102 ms | 123520 KB |
b33 | AC | 129 ms | 121728 KB |
b34 | AC | 157 ms | 121728 KB |
b35 | AC | 157 ms | 121728 KB |
b36 | AC | 127 ms | 121600 KB |
b37 | AC | 124 ms | 121600 KB |
b38 | AC | 129 ms | 121728 KB |
b39 | AC | 131 ms | 121728 KB |
b40 | AC | 131 ms | 121600 KB |
b41 | AC | 122 ms | 121728 KB |
b42 | AC | 126 ms | 121600 KB |
b43 | AC | 124 ms | 121600 KB |
b44 | AC | 120 ms | 121728 KB |
b45 | AC | 102 ms | 123264 KB |
b46 | AC | 102 ms | 123392 KB |
b47 | AC | 102 ms | 123520 KB |
b48 | AC | 102 ms | 123520 KB |
b49 | AC | 102 ms | 123520 KB |
b50 | AC | 89 ms | 121472 KB |
b51 | AC | 87 ms | 121472 KB |
b52 | AC | 87 ms | 121472 KB |
b53 | AC | 86 ms | 121472 KB |
b54 | AC | 86 ms | 121472 KB |
b55 | AC | 104 ms | 122496 KB |