QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#758170#9566. Topologypiaoyun#WA 1ms30396kbC++142.1kb2024-11-17 16:24:152024-11-17 16:24:15

Judging History

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

  • [2024-11-17 16:24:15]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:30396kb
  • [2024-11-17 16:24:15]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int MAXN = 5e3 + 10;
const int MOD = 998244353;
vector<int> p[MAXN];
int a[MAXN];
int dp[MAXN][MAXN];
int g[MAXN][MAXN];

int fac[MAXN];
int inv[MAXN];

int f[MAXN];
int sz[MAXN];
int fac_of_child[MAXN];
int ans[MAXN];
int N;

int quick_pow(int x, int k){
    int ret = 1;
    while(k){
        if(k & 1) ret = ret * x % MOD;
        x = x * x % MOD;
        k >>= 1;
    }
    return ret;
}

int Comb(int n,int m){
    return fac[n] * inv[m] % MOD * inv[n-m] % MOD;
}

void dfs(int u){
    sz[u] = 0; f[u] = 1; fac_of_child[u] = 1;
    for(auto v : p[u]){
        dfs(v);
        f[u] = f[u] * Comb(sz[u] + sz[v],sz[v]) % MOD * f[v] % MOD;
        fac_of_child[u] = fac_of_child[u] * f[v] % MOD;
        sz[u] += sz[v];
    }
    sz[u]++;
    // cout << u << " " << f[u] << endl;
}

int getInv(int x){
    return quick_pow(x, MOD - 2);
}

void calc(int u){
    ans[u] = dp[u][u] * Comb(N - u, sz[u] - 1) % MOD * f[u];
    int tot = N - sz[u] + 1;
    for(auto v : p[u]){
        int t = fac_of_child[u] * getInv(f[v]);
        int other_child_sz = sz[u] - sz[v] - 1;
        for(int k = 1; k <= tot; k++){
            g[u][k] = dp[u][k] * t % MOD * Comb(tot - k + other_child_sz, other_child_sz) % MOD;
            g[u][k] = (g[u][k] + g[u][k-1]) % MOD;
        }
        for(int k = tot + 1; k <= N - sz[v] + 1; k++){
            g[u][k] = g[u][k-1];
        }
        for(int k = 1; k <= N - sz[v] + 1; k++){
            dp[v][k] = g[u][k-1];
            //cout << v << " " << k << " " << dp[v][k] << endl;
        }
        calc(v);
    }
}

signed main(){
    cin >> N;
    for(int i = 2; i <= N; i++){
        cin >> a[i];
        p[a[i]].push_back(i);
    }
    fac[0] = inv[0] = 1;
    for(int i = 1; i < MAXN; i++){
        fac[i] = fac[i-1] * i % MOD;
    }
    inv[MAXN - 1] = quick_pow(fac[MAXN - 1], MOD - 2);
    for(int i = MAXN - 2; i >= 1; i--){
        inv[i] = inv[i + 1] * (i + 1) % MOD;
    }
    dfs(1);
    dp[1][1] = 1;
    calc(1);
    for(int i = 1; i <= N; i++){
        cout << ans[i] << " ";
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 8008kb

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: 5856kb

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: 5888kb

input:

2
1

output:

1 1 

result:

ok 2 number(s): "1 1"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 30396kb

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 110913016431 5423731297305318 155909709328975828 163438188701960677 -63795594211897548 -55296215449673184 -9076521123480330 70656806633320842 -18356607363379210 561340974200794704 672165661611032137 777847101970246812 125064283680 -106861598066476526 -10163868541893697 -108767573...

result:

wrong answer 3rd numbers differ - expected: '107893248', found: '110913016431'