QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #797550 | #9566. Topology | Euphoria_# | WA | 2ms | 71800kb | C++14 | 2.3kb | 2024-12-03 11:56:04 | 2024-12-03 11:56:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n;
int fa[1000010];
long long f[1000010];
long long dp[5010][5010];
long long sum[5010][5010];
long long C[5010][5010];
int cnt,head[1000010];
int sz[1000010];
struct Edge
{
int to,next;
}edge[1000010];
void add(int u,int v)
{
edge[++cnt].to=v,edge[cnt].next=head[u],head[u]=cnt;
}
long long pd(long long x)
{
if(x>=mod) return x-mod;
return x;
}
void p(long long &x)
{
if(x>=mod) x-=mod;
return ;
}
void get_f(int u,int fa)
{
sz[u]=0,f[u]=1;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa) continue;
get_f(v,u),f[u]=f[u]*f[v]%mod*C[sz[u]+sz[v]][sz[v]]%mod;
sz[u]+=sz[v];
}
sz[u]++;
return ;
}
void dfs(int u,int fa)
{
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa) continue;
int nowsize=0;
long long nowval=1;
for(int i=head[u];i;i=edge[i].next)
{
int to=edge[i].to;
if(to==v||to==fa) continue;
(nowval*=f[to]*C[nowsize+sz[to]][sz[to]]%mod)%=mod;
nowsize+=sz[to];
}
for(int now=1;now<=n-sz[u]+1;now++)
{
// long long nowsum=0;
// for(int lst=0;lst<now;lst++) p(nowsum+=dp[u][lst]);
// dp[v][now]=nowsum*nowval%mod*C[n-sz[u]+1-now+nowsize][nowsize]%mod;
dp[v][now]=sum[u][now-1]*nowval%mod*C[n-sz[u]+1-now+nowsize][nowsize]%mod;
sum[v][now]=dp[v][now];
// if(v==2) printf("%d %lld %lld %lld\n",now,dp[v][now],nowsum,nowval);
}
for(int i=1;i<=n;i++) p(sum[v][i]+=sum[v][i-1]);
dfs(v,u);
}
return ;
}
int main()
{
scanf("%d",&n);
for(int i=2;i<=n;i++) scanf("%d",&fa[i]),add(fa[i],i);
for(int i=0;i<=n;i++) C[i][0]=1;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) C[i][j]=pd(C[i-1][j]+C[i-1][j-1]);
get_f(1,0),dp[1][0]=1;
for(int i=0;i<=n;i++) sum[1][i]=1;
dfs(1,0);
for(int i=1;i<=n;i++)
{
long long nowsum=0;
for(int lst=0;lst<i;lst++) nowsum+=dp[i][lst];
// printf("%lld %lld ",nowsum,f[i]);
printf("%lld ",f[i]*C[n-i][sz[i]-1]%mod*nowsum%mod);
}
printf("\n");
return 0;
}
/*
9
1 1 2 2 3 3 4 5
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 16184kb
input:
4 1 1 2
output:
3 2 1 2
result:
ok 4 number(s): "3 2 1 2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 14256kb
input:
9 1 1 2 2 3 3 4 5
output:
672 420 180 160 152 108 120 170 210
result:
ok 9 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 14176kb
input:
2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 71800kb
input:
500 1 2 3 4 5 6 7 7 8 10 8 10 11 4 11 12 12 17 15 13 21 21 22 5 16 9 24 28 28 19 29 27 17 33 23 3 33 27 30 9 25 34 16 26 30 34 46 45 41 14 43 49 43 35 39 37 26 48 52 58 51 56 51 55 19 48 63 36 67 69 54 60 71 61 29 40 32 77 73 55 66 42 77 72 71 69 62 83 46 64 88 39 83 36 89 94 47 98 57 61 38 80 78 88...
output:
331058271 331058271 107893248 201481008 579367731 934007150 548415590 60830816 948776140 565765713 126668425 603509050 491206892 433369091 271511598 706737964 70425819 69672788 713120782 734952162 267434947 720007515 670449595 828144080 372921049 434477621 877300187 307269573 636190001 793011806 -60...
result:
wrong answer 31st numbers differ - expected: '327684609', found: '-604367301'