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

Judge Result