Submission #23005899

Source Code Expand

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
const int mod=998244353;
vector<int> adj[2002];
llo pre[2002];
int ss[2002];
llo dp[2002][2002];
int tt[2002];
//llo ans=1;
llo n;
void dfs(llo no,llo lev=1,llo par=-1){
	ss[no]=1;
	tt[no]=1;
	//ans=(ans*(n-lev))%mod;
	dp[no][0]=1;
	if(par!=-1 and adj[no].size()==0){
		ss[no]=0;
		return ;
	}
	llo co=0;
	vector<llo> ee;
	pair<llo,llo> ma={-1,-1};
	for(auto j:adj[no]){
		dfs(j,lev+1,no);
		
		
		ee.pb(j);
		ma=max(ma,{ss[j],j});
		continue;
		if(co==1){
			for(int jj=ss[no];jj>=1;jj--){
				dp[no][jj]=dp[j][jj];

			}
			continue;
		}

		co+=1;

		ss[no]+=ss[j];
		tt[no]+=tt[j];
		

		for(int jj=ss[no];jj>=1;jj--){
			for(int i=max(1,-ss[no]+ss[j]-jj);i<=min(ss[j],jj);i++){
				/*if(no==0 and j==1){
					if(jj==1 and i==1){
						cout<<dp[j][i]<<":"<<endl;
						cout<<dp[no][jj-i]<<">"<<endl;
					}
				}*/

				dp[no][jj]=(dp[no][jj]+dp[no][jj-i]*dp[j][i])%mod;
				/*if(no==0 and j==1){
					if(jj==1 and i==1){
						cout<<dp[no][jj]<<endl;
					}
				}*/
			}
		}
	/*	if(no==0){
			for(int jj=0;jj<=ss[no];jj++){
				cout<<dp[0][jj]<<":";
			}
			cout<<endl;

		}*/
	}
	ss[no]+=ss[ma.b];
	tt[no]+=tt[ma.b];
	for(int jj=ss[no];jj>=1;jj--){
		dp[no][jj]=dp[ma.b][jj];

	}
	for(auto j:ee){
		if(j==ma.b){
			continue;
		}
		ss[no]+=ss[j];
		tt[no]+=tt[j];
		

		for(int jj=ss[no];jj>=1;jj--){
			for(int i=max(1,-ss[no]+ss[j]-jj);i<=min(ss[j],jj);i++){
				/*if(no==0 and j==1){
					if(jj==1 and i==1){
						cout<<dp[j][i]<<":"<<endl;
						cout<<dp[no][jj-i]<<">"<<endl;
					}
				}*/

				dp[no][jj]=(dp[no][jj]+dp[no][jj-i]*dp[j][i])%mod;
				/*if(no==0 and j==1){
					if(jj==1 and i==1){
						cout<<dp[no][jj]<<endl;
					}
				}*/
			}
		}
	}
	//cout<<no<<"?"<<ss[no]<<endl;
	//if(no!=0){
		for(int j=ss[no];j>=1;j--){
			dp[no][j]=(dp[no][j]+dp[no][j-1]*(tt[no]-1-(j-1)))%mod;
		}
	//}

}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(int i=1;i<n;i++){
		llo aa;
		cin>>aa;
		aa--;
		adj[aa].pb(i);
	}
	pre[0]=1;
	for(int i=1;i<=2000;i++){
		pre[i]=(pre[i-1]*i)%mod;
	}
	dfs(0);
	llo ans=pre[n];
	/*for(int i=0;i<n;i++){
		for(int j=0;j<=ss[i];j++){
			cout<<dp[i][j]<<",";
		}
		cout<<endl;
	}*/
	for(int i=1;i<=n;i++){
		llo cur=dp[0][i]*pre[n-i];
		cur%=mod;
		//cout<<cur<<":"<<endl;
		if(i%2==1){
			cur=mod-cur;
		}
		ans=(ans+cur)%mod;

	}
	cout<<ans<<endl;







	return 0;
}

Submission Info

Submission Time
Task E - Directed Tree
User kshitij_789
Language C++ (GCC 9.2.1)
Score 700
Code Size 2707 Byte
Status AC
Exec Time 24 ms
Memory 19688 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 2
AC × 47
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt, random_33.txt, random_34.txt, random_35.txt, random_36.txt, random_37.txt, random_38.txt, random_39.txt, random_40.txt, random_41.txt, random_42.txt, random_43.txt, random_44.txt, random_45.txt, sample_01.txt, sample_02.txt
Case Name Status Exec Time Memory
random_01.txt AC 14 ms 11560 KiB
random_02.txt AC 13 ms 11708 KiB
random_03.txt AC 12 ms 11668 KiB
random_04.txt AC 12 ms 11740 KiB
random_05.txt AC 20 ms 11724 KiB
random_06.txt AC 12 ms 11568 KiB
random_07.txt AC 14 ms 11604 KiB
random_08.txt AC 14 ms 11648 KiB
random_09.txt AC 13 ms 11832 KiB
random_10.txt AC 10 ms 11724 KiB
random_11.txt AC 9 ms 10860 KiB
random_12.txt AC 14 ms 11656 KiB
random_13.txt AC 13 ms 11164 KiB
random_14.txt AC 6 ms 6816 KiB
random_15.txt AC 6 ms 6368 KiB
random_16.txt AC 9 ms 6716 KiB
random_17.txt AC 8 ms 8976 KiB
random_18.txt AC 12 ms 10044 KiB
random_19.txt AC 6 ms 7272 KiB
random_20.txt AC 7 ms 5056 KiB
random_21.txt AC 9 ms 7436 KiB
random_22.txt AC 21 ms 11388 KiB
random_23.txt AC 5 ms 5568 KiB
random_24.txt AC 13 ms 11576 KiB
random_25.txt AC 15 ms 11072 KiB
random_26.txt AC 18 ms 18932 KiB
random_27.txt AC 17 ms 17012 KiB
random_28.txt AC 24 ms 19688 KiB
random_29.txt AC 3 ms 4276 KiB
random_30.txt AC 16 ms 13256 KiB
random_31.txt AC 10 ms 8628 KiB
random_32.txt AC 10 ms 10328 KiB
random_33.txt AC 12 ms 9616 KiB
random_34.txt AC 2 ms 4060 KiB
random_35.txt AC 8 ms 6800 KiB
random_36.txt AC 5 ms 7072 KiB
random_37.txt AC 6 ms 6544 KiB
random_38.txt AC 9 ms 10492 KiB
random_39.txt AC 4 ms 4716 KiB
random_40.txt AC 11 ms 10568 KiB
random_41.txt AC 2 ms 3636 KiB
random_42.txt AC 14 ms 11736 KiB
random_43.txt AC 12 ms 11100 KiB
random_44.txt AC 11 ms 9160 KiB
random_45.txt AC 15 ms 11508 KiB
sample_01.txt AC 3 ms 3680 KiB
sample_02.txt AC 3 ms 3676 KiB