QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#739142 | #9566. Topology | ucup-team5296 | WA | 4ms | 14540kb | C++20 | 2.7kb | 2024-11-12 21:00:01 | 2024-11-12 21:00:03 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define eb emplace_back
#define ep emplace
#define pii pair<int,int>
#define fi first
#define se second
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define mems(arr,x) memset(arr,x,sizeof(arr))
#define memc(arr1,arr2) memcpy(arr1,arr2,sizeof(arr2))
using namespace std;
const int maxn=5010,mod=998244353;
int n;
int p[maxn];
namespace FastMod{
inline void madd(int &x,int y){x+=y;(x>=mod)&&(x-=mod);}
inline void mdel(int &x,int y){x-=y;(x<0)&&(x+=mod);}
inline void mmul(int &x,int y){x=1ll*x*y%mod;}
inline int imadd(int x,int y){madd(x,y);return x;}
inline int imdel(int x,int y){mdel(x,y);return x;}
inline int immul(int x,int y){mmul(x,y);return x;}
inline int qpow(int x,int y){int res=1;while(y){if(y&1) res=1ll*res*x%mod;x=1ll*x*x%mod;y>>=1;}return res;}
}
using namespace FastMod;
namespace Graph{
const int maxm=maxn<<1;
#define go(x,i) for(int i=head[x];i;i=e[i].nxt)
int cnt=1;
int head[maxn];
struct edge{int nxt,to;}e[maxm];
inline void add(int u,int v){e[++cnt]={head[u],v};head[u]=cnt;}
inline void adde(int u,int v){add(u,v);add(v,u);}
}
using namespace Graph;
int fac[maxn],inv[maxn];
void init(){
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=immul(fac[i-1],i);
inv[n]=qpow(fac[n],mod-2);
for(int i=n-1;~i;i--) inv[i]=immul(inv[i+1],i+1);
}
inline int C(int x,int y){return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;}
int siz[maxn],isiz[maxn];
int dp[maxn][maxn]; // dp[i][j] 表示拓扑序的第 j 位为 i 的方案数
void dfs1(int u,int fa){
siz[u]=isiz[u]=1;
go(u,i){
int t=e[i].to;
if(t==fa) continue;
dfs1(t,u);
siz[u]+=siz[t];
mmul(isiz[u],isiz[t]);
}
mmul(isiz[u],qpow(siz[u],mod-2));
}
int sum[maxn];
void dfs2(int u,int fa){
if(p[u]==1) dp[u][1]=1;
else if(fa){
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+dp[fa][i];
for(int i=1;i<=n;i++) dp[u][i]=immul(sum[i-1],C(n-siz[u]-i,siz[fa]-siz[u]-1));
}
go(u,i){
int t=e[i].to;
if(t==fa) continue;
dfs2(t,u);
}
}
int solve(int u){
int res=immul(fac[siz[u]],isiz[u]);
if(u==1) return res;
int s=0;
for(int i=1;i<u;i++) madd(s,dp[u][i]);
mmul(s,C(n-u,siz[u]-1));
while(u^1){
int tmp=1ll*isiz[p[u]]*siz[p[u]]%mod*qpow(isiz[u],mod-2)%mod;
mmul(res,immul(fac[siz[p[u]]-siz[u]-1],tmp));
u=p[u];
}
return immul(s,res);
}
int main(){
scanf("%d",&n);
init();
for(int i=2;i<=n;i++){
scanf("%d",&p[i]);
adde(p[i],i);
}
dfs1(1,0);
dfs2(1,0);
for(int i=1;i<=n;i++) printf("%d ",solve(i));
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3928kb
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: 3892kb
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: 0ms
memory: 3860kb
input:
2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #4:
score: -100
Wrong Answer
time: 4ms
memory: 14540kb
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 222527183 -516314086 896615741 271511598 -441996634 531708476 -157727005 -944173445 43242309 -436514969 428784312 -338014422 981601077 372921049 -507456798 -549219328 -488548991 -860741287 -8...
result:
wrong answer 12th numbers differ - expected: '603509050', found: '222527183'