Submission #61272445

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
const int N=1e5+5;
int n;
int p[N];
int h[N];
int g[N];
ll pw(ll x,ll y){
	if(y==0) return 1;
	if(y%2) return x*pw(x,y-1)%mod;
	ll res=pw(x,y/2);
	return res*res%mod;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> n;
	for(int i=2; i<=n ;i++){
		cin >> p[i];
		h[i]=h[p[i]]+1;
		g[h[i]]++;
	}
	g[0]++;
	ll cum=0;
	ll ans=n*pw(n-1,n-1)%mod;
	for(int i=n-1; i>=0 ;i--){
		if(i!=n-1) ans=(ans+n*pw(n-1,n-i-2)%mod*cum)%mod;
		ans=(ans+pw(n-1,n-i-1)*g[i])%mod;
		cum+=g[i];
	}
	cout << ans << '\n';
}

Submission Info

Submission Time
Task B - Odd Namori
User mulgokizary
Language C++ 20 (gcc 12.2)
Score 1000
Code Size 670 Byte
Status AC
Exec Time 30 ms
Memory 4484 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 4
AC × 28
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_n_small_00.txt, 01_n_small_01.txt, 01_n_small_02.txt, 01_n_small_03.txt, 01_n_small_04.txt, 01_n_small_05.txt, 01_n_small_06.txt, 01_n_small_07.txt, 01_n_small_08.txt, 01_n_small_09.txt, 02_random_00.txt, 02_random_01.txt, 02_random_02.txt, 02_random_03.txt, 02_random_04.txt, 02_random_05.txt, 02_random_06.txt, 02_random_07.txt, 02_random_08.txt, 02_random_09.txt, 03_path_00.txt, 03_path_01.txt, 04_star_00.txt, 04_star_01.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1 ms 3472 KiB
00_sample_01.txt AC 1 ms 3436 KiB
00_sample_02.txt AC 1 ms 3464 KiB
00_sample_03.txt AC 1 ms 3460 KiB
01_n_small_00.txt AC 1 ms 3400 KiB
01_n_small_01.txt AC 1 ms 3516 KiB
01_n_small_02.txt AC 1 ms 3376 KiB
01_n_small_03.txt AC 1 ms 3456 KiB
01_n_small_04.txt AC 1 ms 3436 KiB
01_n_small_05.txt AC 1 ms 3404 KiB
01_n_small_06.txt AC 1 ms 3460 KiB
01_n_small_07.txt AC 1 ms 3456 KiB
01_n_small_08.txt AC 1 ms 3512 KiB
01_n_small_09.txt AC 1 ms 3404 KiB
02_random_00.txt AC 24 ms 4060 KiB
02_random_01.txt AC 30 ms 4256 KiB
02_random_02.txt AC 5 ms 3484 KiB
02_random_03.txt AC 29 ms 4300 KiB
02_random_04.txt AC 7 ms 3664 KiB
02_random_05.txt AC 30 ms 4224 KiB
02_random_06.txt AC 3 ms 3532 KiB
02_random_07.txt AC 30 ms 4160 KiB
02_random_08.txt AC 9 ms 3776 KiB
02_random_09.txt AC 30 ms 4196 KiB
03_path_00.txt AC 12 ms 3892 KiB
03_path_01.txt AC 29 ms 4484 KiB
04_star_00.txt AC 6 ms 3648 KiB
04_star_01.txt AC 28 ms 4220 KiB