QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#764624#7864. Random Tree Parkingqsc114AC ✓280ms88120kbC++114.4kb2024-11-20 09:59:432024-11-20 10:00:00

Judging History

你现在查看的是最新测评结果

  • [2024-11-20 10:00:00]
  • 评测
  • 测评结果:AC
  • 用时:280ms
  • 内存:88120kb
  • [2024-11-20 09:59:43]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5,MOD=998244353,g=3;
#define ll long long
int rev[MAXN<<1];
ll w[(1<<21)+5],ninv[MAXN],fac[MAXN],ifac[MAXN];
ll qpow(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1)ans*=a,ans%=MOD;
		a*=a,a%=MOD;b>>=1;
	}
	return ans;
}
void init()
{
	ll stp=qpow(g,(MOD-1)/(1<<21));
	w[0]=1;
	for(int i=1;i<(1<<21);i++)
		w[i]=w[i-1]*stp%MOD;
	ninv[1]=1;
	for(int i=2;i<=MAXN-5;i++)
		ninv[i]=(MOD-MOD/i)*ninv[MOD%i]%MOD;
	fac[0]=ifac[0]=1;
	for(int i=1;i<=MAXN-5;i++)
		fac[i]=fac[i-1]*i%MOD,
		ifac[i]=ifac[i-1]*ninv[i]%MOD;
}
struct node
{
	int len;
	vector<ll> a;
	void rsiz(int x)
	{
		len=x;
		a.resize(x);
	}
	void srk()
	{
		for(int i=len-1;i>=0;i--)
			if(a[i])
				{len=i+1;break;}
		a.resize(len);
	}
};
node makenode(int c)
{
	node x;x.rsiz(1);
	x.a[0]=c;
	return x;
}
node operator+(node x,node y)
{
	if(x.len<y.len)swap(x,y);
	for(int i=0;i<y.len;++i)
	{
		x.a[i]+=y.a[i];
		if(x.a[i]>MOD)x.a[i]-=MOD;
	}
	return x;
}
node operator-(node x,node y)
{
	int flag=0;
	if(x.len<y.len)swap(x,y),flag=1;
	for(int i=0;i<y.len;i++)
	{
		if(flag)x.a[i]=y.a[i]-x.a[i];
		if(x.a[i]<0)x.a[i]+=MOD;
	}
	for(int i=y.len;i<x.len;i++)
		x.a[i]=MOD-x.a[i];
	return x;
}
node operator*(node x,ll c)
{
	for(int i=0;i<x.len;i++)
		x.a[i]=x.a[i]*c%MOD;
	return x;
}
node operator*(ll c,node x)
{
	for(int i=0;i<x.len;i++)
		x.a[i]=x.a[i]*c%MOD;
	return x;
}
node operator>>(node x,int c)
{
	for(int i=0;i<=x.len-c-1;i++)
		x.a[i]=x.a[i+c];
	return x;
}
void pre(int rev[],int len)
{
	rev[0]=0;
	rev[1]=(len>>1);
	for(int i=2;i<len;i++)
	{
		rev[i]=rev[i>>1]>>1;
		if(i&1)rev[i]+=(len>>1);
	}
}
void ntt(node &x,int r)
{
	int len=x.len;
	pre(rev,len);
	for(int i=0;i<len;i++)
		if(i<rev[i])swap(x.a[i],x.a[rev[i]]);
	for(int k=2;k<=len;k<<=1)
	{
		int d=k>>1,step=(1<<21)/k;
		for(int i=0;i<len;i+=k)
		{
			int wn=0;
			for(int j=i;j<i+d;j++)
			{
				ll u=x.a[j],v=x.a[j+d];
				x.a[j]=(u+w[wn]*v)%MOD;
				x.a[j+d]=(u-w[wn]*v)%MOD;
				wn+=step;
			}
		}
	}
	if(r==-1)
	{
		reverse(x.a.begin()+1,x.a.end());
		ll inv=qpow(len,MOD-2);
		for(int i=0;i<len;i++)
			x.a[i]=x.a[i]*inv%MOD;
	}
}
int getlen(int x,int y)
{
	x+=y-1;
	int res=1;
	while(res<x)res<<=1;
	return res;
}
node operator*(node x,node y)
{
	int len=getlen(x.len,y.len);
	x.rsiz(len),y.rsiz(len);
	ntt(x,1),ntt(y,1);
	for(int i=0;i<len;i++)
		x.a[i]=x.a[i]*y.a[i]%MOD;
	ntt(x,-1);
	x.srk();
	return x;
}
node inv(node x)
{
	if(x.len==1)
	{
		x.a[0]=qpow(x.a[0],MOD-2);
		return x;
	}
	node y=x;y.rsiz((x.len+1)/2);
	node f0=inv(y);
	int xlen=x.len,len=getlen(f0.len*2,x.len);
	f0.rsiz(len),x.rsiz(len);
	ntt(f0,1),ntt(x,1);
	for(int i=0;i<len;i++)
		x.a[i]=(2*f0.a[i]-f0.a[i]*f0.a[i]%MOD*x.a[i])%MOD;
	ntt(x,-1);
	x.rsiz(xlen);
	return x;
}
node sqr(node x)
{
	if(x.len==1)
	{
		x.a[0]=1;
		return x;
	}
	node y=x;y.rsiz((x.len+1)/2);
	node f0=sqr(y);
	int xlen=x.len,len=getlen(xlen,f0.len*2);
	f0.rsiz(len);
	node f1=inv(f0);
	len=getlen(len,f1.len);
	x.rsiz(len);f1.rsiz(len);f0.rsiz(len);
	ntt(f0,1),ntt(f1,1),ntt(x,1);
	ll hlf=qpow(2,MOD-2);
	for(int i=0;i<len;i++)
		x.a[i]=(f0.a[i]*f0.a[i]%MOD+x.a[i])*hlf%MOD,
		x.a[i]=x.a[i]*f1.a[i]%MOD;
	ntt(x,-1);
	x.rsiz(xlen);
	return x;
}
node drv(node x)
{
	int len=x.len;
	for(int i=0;i<len-1;i++)
		x.a[i]=x.a[i+1]*(i+1)%MOD;
	x.rsiz(len-1);
	return x;
}
node idrv(node x)
{
	int len=x.len;
	x.rsiz(len+1);
	for(int i=len-1;i>=1;i--)
		x.a[i]=x.a[i-1]*qpow(i,MOD-2)%MOD;
	x.a[0]=0;
	return x;
}
node lne(node x)
{
	int len=x.len;
	x=drv(x)*inv(x);
	x.rsiz(len);x=idrv(x);
	x.rsiz(len);
	return x;
}
node exp(node x)
{
	if(x.len==1)
	{
		x.a[0]=1;
		return x;
	}
	int len=x.len;
	node y=x;y.rsiz((len+1)/2);
	node f0=exp(y);f0.rsiz(len);
	node f1=lne(f0);
	x=f0*(makenode(1)-f1+x);x.rsiz(len);
	return x;
}
int n,fa[MAXN],dep[MAXN];
node f[MAXN];
vector<int> ve[MAXN];
void dfs(int o)
{
	dep[o]=dep[fa[o]]+1;
	for(auto u:ve[o])
		dfs(u);
}
void calc(int o)
{
	f[o].rsiz(dep[o]+1);
	for(int i=0;i<=dep[o];i++)
		f[o].a[i]=ifac[i];
	for(auto u:ve[o])
	{
		calc(u);
		f[o]=f[o]*f[u];
	}
	f[o]=f[o]>>1;
	f[o].rsiz(dep[o]);
}
int main()
{
	init();
	cin>>n;
	for(int i=2;i<=n;i++)
		scanf("%d",fa+i),ve[fa[i]].push_back(i);
	dfs(1);
	calc(1);
	cout<<(f[1].a[0]*fac[n]%MOD+MOD)%MOD;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 17ms
memory: 64312kb

input:

3
1 1

output:

12

result:

ok 1 number(s): "12"

Test #2:

score: 0
Accepted
time: 23ms
memory: 63776kb

input:

3
1 2

output:

16

result:

ok 1 number(s): "16"

Test #3:

score: 0
Accepted
time: 3ms
memory: 63444kb

input:

4
1 2 3

output:

125

result:

ok 1 number(s): "125"

Test #4:

score: 0
Accepted
time: 15ms
memory: 64472kb

input:

8
1 2 3 1 3 4 3

output:

1198736

result:

ok 1 number(s): "1198736"

Test #5:

score: 0
Accepted
time: 20ms
memory: 64948kb

input:

15
1 2 2 2 2 3 3 2 7 7 3 10 3 13

output:

938578089

result:

ok 1 number(s): "938578089"

Test #6:

score: 0
Accepted
time: 20ms
memory: 64504kb

input:

100
1 1 1 3 5 5 5 5 9 9 3 2 11 14 9 8 16 8 18 18 20 10 12 2 22 21 27 28 29 6 2 21 2 20 21 11 16 19 9 25 39 8 14 19 6 38 22 19 25 13 3 27 19 51 23 18 45 30 30 22 24 16 12 61 42 24 3 3 53 40 59 72 6 23 1 64 41 13 71 75 30 64 11 55 70 60 32 84 25 4 69 49 15 42 72 31 71 23 58

output:

426063005

result:

ok 1 number(s): "426063005"

Test #7:

score: 0
Accepted
time: 16ms
memory: 63596kb

input:

500
1 1 3 3 3 4 3 5 2 5 8 4 12 11 8 14 1 12 7 16 7 7 17 10 8 26 7 4 13 21 6 7 20 34 35 24 25 23 25 39 20 30 13 43 43 35 45 34 7 4 11 23 11 43 35 27 6 2 3 11 37 42 27 37 62 42 41 43 63 4 57 17 18 8 11 23 72 74 41 49 76 44 50 81 46 18 45 5 8 88 77 27 35 11 52 18 32 85 57 25 32 22 39 35 43 26 63 7 62 2...

output:

105022837

result:

ok 1 number(s): "105022837"

Test #8:

score: 0
Accepted
time: 19ms
memory: 65104kb

input:

2000
1 1 2 4 4 4 1 5 9 4 5 9 9 4 15 1 11 18 11 2 4 22 10 23 18 15 6 25 25 19 15 28 32 17 29 24 35 11 32 20 25 8 7 12 27 29 40 21 23 47 24 8 6 24 53 43 9 10 48 18 16 16 10 45 42 33 20 27 33 47 41 22 37 4 38 23 8 29 14 54 49 74 60 56 45 32 11 4 58 16 71 29 49 32 31 95 38 2 89 73 91 65 26 12 94 35 1 73...

output:

510693456

result:

ok 1 number(s): "510693456"

Test #9:

score: 0
Accepted
time: 30ms
memory: 65224kb

input:

10000
1 2 1 1 2 1 4 3 5 6 1 8 8 3 2 15 4 14 10 9 9 15 17 5 21 9 11 24 17 20 17 16 4 13 10 10 36 2 8 29 34 40 8 13 27 5 1 18 16 4 40 47 4 8 9 1 54 40 38 41 46 52 31 21 21 14 49 49 46 22 14 59 71 37 30 18 37 30 36 56 24 56 48 17 75 68 68 6 65 87 48 52 8 26 94 89 29 32 40 77 51 6 9 78 1 48 100 69 85 89...

output:

158503783

result:

ok 1 number(s): "158503783"

Test #10:

score: 0
Accepted
time: 280ms
memory: 88120kb

input:

100000
1 1 1 2 4 4 7 8 6 9 7 8 12 10 15 15 9 12 9 16 9 13 11 18 11 8 6 23 22 28 8 29 12 24 14 9 33 5 17 4 33 29 41 19 37 34 19 41 15 21 20 13 36 25 34 38 2 56 33 53 40 36 26 28 34 7 19 66 35 43 52 47 53 32 61 11 55 10 78 75 43 80 71 16 20 68 27 41 80 33 69 50 71 7 5 26 24 78 62 17 76 15 10 11 56 64 ...

output:

937583571

result:

ok 1 number(s): "937583571"

Test #11:

score: 0
Accepted
time: 239ms
memory: 85692kb

input:

100000
1 2 1 2 5 3 5 4 6 8 2 1 6 2 5 5 1 6 12 12 15 11 23 3 4 13 3 22 8 5 13 12 10 9 6 27 37 22 14 24 12 26 15 30 2 27 43 4 47 9 42 5 33 26 13 54 17 32 23 15 34 36 14 49 41 25 14 35 22 35 51 50 17 22 38 54 71 41 69 44 61 18 77 3 78 53 74 70 67 8 18 10 88 2 1 74 36 15 76 62 7 70 89 24 72 77 15 44 49 ...

output:

264669337

result:

ok 1 number(s): "264669337"

Test #12:

score: 0
Accepted
time: 245ms
memory: 85900kb

input:

100000
1 1 3 2 2 6 7 6 3 4 10 1 2 14 12 16 3 2 19 20 3 2 12 17 6 17 16 9 27 18 23 21 2 31 18 13 6 17 39 13 25 18 29 11 42 17 10 34 22 9 33 31 52 45 5 54 43 52 56 4 5 47 63 51 41 54 28 65 31 70 2 63 59 53 53 40 39 5 46 71 13 6 41 31 57 4 82 62 78 59 87 72 92 9 5 69 90 92 19 15 78 41 39 23 12 1 47 49 ...

output:

399299126

result:

ok 1 number(s): "399299126"

Test #13:

score: 0
Accepted
time: 245ms
memory: 84812kb

input:

100000
1 1 1 4 5 5 3 7 6 1 7 8 8 11 11 13 7 7 1 1 13 20 21 22 22 19 8 2 29 28 4 27 8 16 30 4 5 14 21 35 29 32 35 22 14 23 41 24 33 12 31 39 4 40 24 5 38 46 20 23 37 5 27 39 32 41 26 50 33 15 50 40 40 23 52 58 31 16 25 60 36 72 29 33 48 1 82 1 25 57 15 69 5 78 29 81 36 46 97 38 15 7 39 51 19 80 29 77...

output:

58289876

result:

ok 1 number(s): "58289876"

Test #14:

score: 0
Accepted
time: 224ms
memory: 85380kb

input:

100000
1 1 1 1 4 1 7 2 4 8 6 3 2 9 15 15 5 5 7 1 12 15 4 19 7 8 15 21 26 28 13 20 14 21 30 27 21 2 3 14 1 33 33 8 41 25 11 38 35 35 35 5 16 29 16 9 24 39 13 12 3 58 20 44 3 43 53 57 13 23 44 43 14 4 23 69 27 73 22 55 25 64 52 40 71 48 56 56 8 68 27 30 92 46 18 7 58 30 65 69 61 55 38 92 33 102 80 2 2...

output:

861492056

result:

ok 1 number(s): "861492056"

Test #15:

score: 0
Accepted
time: 256ms
memory: 85588kb

input:

100000
1 1 2 3 2 2 5 8 7 4 1 3 5 11 15 2 9 8 19 5 19 11 15 19 19 11 26 3 13 15 30 1 18 28 16 33 9 23 15 2 3 36 7 11 44 31 40 15 46 7 8 5 23 36 22 12 2 28 23 14 11 40 21 18 60 24 32 42 50 57 21 27 60 54 9 63 76 56 22 59 40 41 31 58 27 68 10 45 70 54 46 29 68 6 4 61 11 7 60 56 69 92 69 5 88 71 46 21 7...

output:

528382031

result:

ok 1 number(s): "528382031"

Test #16:

score: 0
Accepted
time: 223ms
memory: 85096kb

input:

100000
1 1 3 1 1 5 4 5 3 3 6 4 1 8 10 15 5 14 5 16 9 13 14 13 8 15 26 17 1 21 11 31 18 16 21 27 14 32 9 27 30 30 3 41 33 26 47 25 26 6 24 15 11 15 6 49 48 25 23 56 3 38 31 28 54 14 17 45 60 64 24 21 14 30 20 30 38 8 13 43 37 11 83 78 75 12 30 66 37 85 24 77 72 71 49 78 88 73 25 68 19 51 79 43 93 21 ...

output:

316789948

result:

ok 1 number(s): "316789948"

Test #17:

score: 0
Accepted
time: 251ms
memory: 86196kb

input:

100000
1 2 1 2 5 4 3 8 5 8 7 6 3 10 15 12 10 4 17 15 16 13 11 1 15 10 4 16 21 11 25 11 15 4 9 21 18 16 17 29 39 3 39 1 34 5 1 14 44 5 15 16 12 15 42 28 45 32 8 33 7 32 61 9 8 34 54 66 59 61 51 51 37 40 30 61 36 36 45 18 75 27 27 45 45 53 50 77 26 89 72 41 15 18 56 53 64 6 34 33 9 90 41 50 8 4 58 101...

output:

846732448

result:

ok 1 number(s): "846732448"

Test #18:

score: 0
Accepted
time: 217ms
memory: 85024kb

input:

100000
1 1 1 3 3 6 5 7 1 3 11 6 3 2 4 4 12 1 6 10 15 8 8 20 24 10 3 5 25 4 10 13 18 30 19 11 9 6 8 24 16 5 17 2 42 33 35 3 26 42 7 42 30 17 6 41 57 53 8 19 41 50 4 16 13 45 28 50 53 22 20 2 9 30 62 25 43 76 2 41 67 74 16 2 43 64 17 28 61 15 35 33 12 60 29 64 51 33 16 18 16 15 45 18 77 40 10 87 70 72...

output:

994347719

result:

ok 1 number(s): "994347719"

Test #19:

score: 0
Accepted
time: 246ms
memory: 86352kb

input:

100000
1 1 1 4 3 3 5 8 8 1 4 9 9 14 6 12 5 3 2 9 14 4 15 11 14 14 12 18 3 22 25 1 23 1 15 8 21 35 31 34 15 23 30 13 32 18 22 33 32 18 36 46 36 27 45 16 4 35 48 12 29 1 59 64 33 12 4 1 53 8 29 16 18 67 75 7 54 18 74 21 55 69 47 54 42 56 2 85 3 90 81 42 15 90 9 41 72 68 43 58 28 87 38 22 39 29 26 44 2...

output:

946042832

result:

ok 1 number(s): "946042832"

Test #20:

score: 0
Accepted
time: 101ms
memory: 72856kb

input:

40000
1 2 2 4 1 6 5 3 3 6 3 3 4 6 10 12 1 18 18 4 11 3 9 14 25 13 14 18 4 3 1 6 13 16 9 17 37 13 38 7 10 36 13 8 22 3 17 1 20 12 33 37 8 10 25 35 41 52 10 35 36 59 20 25 32 62 18 5 3 22 66 13 2 52 38 30 62 18 35 77 51 58 32 34 44 2 70 85 46 2 80 84 67 91 91 80 19 13 42 99 75 36 38 51 62 93 96 37 96 ...

output:

599775439

result:

ok 1 number(s): "599775439"

Extra Test:

score: 0
Extra Test Passed