QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#783238 | #9566. Topology | DarwinA66 | WA | 121ms | 28176kb | C++20 | 2.1kb | 2024-11-26 02:44:29 | 2024-11-26 02:44:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=5010;
int mod=998244353;
int n;
vector<int>G[N];
int L[N];
int sz[N];
int p[N];
int f[N];
int g[N][N];
int dp[N][N];
int S[N][N];
int ans[N];
int fast_pow(int a,int m)
{
int base=a;
int res=1;
while(m)
{
if(m&1)res=(int)((res*1ll*base)%mod);
base=(int)((base*1ll*base)%mod);
m>>=1;
}
return res;
}
int mod_inverse(int x)
{
return (int)(fast_pow(x,mod-2));
}
int C(int x,int y)
{
return (int)((((L[x]*1ll*mod_inverse(L[y]))%mod)*1ll*mod_inverse(L[x-y]))%mod);
}
void dfs_1(int u,int fa)
{
int temp=L[sz[u]-1];
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
dfs_1(v,u);
temp=(int)((temp*1ll*f[v])%mod);
temp=(int)((temp*1ll*mod_inverse(L[sz[v]]))%mod);
//printf("%d\n",temp);
}
f[u]=temp;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
g[u][v]=(int)(((f[u]*1ll*mod_inverse(f[v]))%mod)*mod_inverse(C(sz[u]-1,sz[v]))%mod);
}
}
void dfs_2(int u,int fa)
{
if(u!=1)
{
for(int i=1;i<=n;i++)
{
S[fa][i]=(int)(((S[fa][i-1]*1ll+(dp[fa][i]*1ll*C(n-sz[u]-i,sz[fa]-sz[u]-1))%mod))%mod);
dp[u][i]=(int)(g[fa][u]*1ll*S[fa][i-1])%mod;
}
}
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
dfs_2(v,u);
}
}
int main()
{
scanf("%d",&n);
L[0]=1;
for(int i=1;i<=n;i++)L[i]=(int)((i*1ll*L[i-1])%mod);
for(int i=2;i<=n;i++)
{
int x;
scanf("%d",&x);
p[i]=x;
G[x].push_back(i);
}
for(int i=1;i<=n;i++)sz[i]=1;
for(int i=n;i>=2;i--)sz[p[i]]+=sz[i];
dp[1][1]=1;
dfs_1(1,0);
dfs_2(1,0);
for(int i=1;i<=n;i++)
{
ans[i]=(int)((((dp[i][i]*1ll*f[i])%mod)*1ll*C(n-i,sz[i]-1))%mod);
}
/*
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
printf("%d ",g[i][j]);
}
printf("\n");
}
*/
for(int i=1;i<=n;i++)
{
printf("%d ",ans[i]);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7976kb
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: 1ms
memory: 7992kb
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: 1ms
memory: 8076kb
input:
2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #4:
score: -100
Wrong Answer
time: 121ms
memory: 28176kb
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 976206204 -733050129 -452709047 775433504 731246160 787128864 87788653 -880744685 771202370 -670386694 -358560681 770885020 -443811420 25245389 -694908402 -821884846 -479395850 -411352008 531578708 -789883292 -410125558 -681239269 853526289 800538179 419420999...
result:
wrong answer 5th numbers differ - expected: '579367731', found: '976206204'