QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#739142#9566. Topologyucup-team5296WA 4ms14540kbC++202.7kb2024-11-12 21:00:012024-11-12 21:00:03

Judging History

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

  • [2024-11-12 21:00:03]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:14540kb
  • [2024-11-12 21:00:01]
  • 提交

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'