QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#758173#9566. Topologypiaoyun#WA 7ms27736kbC++142.2kb2024-11-17 16:26:492024-11-17 16:26:49

Judging History

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

  • [2024-11-17 16:26:49]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:27736kb
  • [2024-11-17 16:26:49]
  • 提交

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] % MOD;
    int tot = N - sz[u] + 1;
    for(auto v : p[u]){
        int t = fac_of_child[u] * getInv(f[v]) % MOD;
        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: 1ms
memory: 5848kb

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

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

input:

2
1

output:

1 1 

result:

ok 2 number(s): "1 1"

Test #4:

score: 0
Accepted
time: 7ms
memory: 26732kb

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 327...

result:

ok 500 numbers

Test #5:

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

input:

500
1 2 3 4 5 2 6 8 9 10 11 12 13 14 15 16 7 18 19 17 21 20 22 24 25 26 23 27 29 30 2 28 31 34 35 36 37 38 39 33 40 42 41 43 45 46 17 47 49 35 50 52 44 53 9 55 54 57 58 59 61 60 62 64 65 66 67 68 69 70 63 71 27 73 25 70 75 78 79 80 75 80 81 84 72 86 87 85 89 90 91 88 92 16 71 93 53 94 99 10 100 12 9...

output:

199957339 199957339 713415395 633706456 352131089 624197058 360461813 532766543 643300762 951160691 515628617 162173363 188718163 899871076 591019765 913659763 516547362 997687530 555134171 277981670 434565875 428443692 950912211 201268221 799265651 31491534 581175237 513698743 795109450 730574236 6...

result:

wrong answer 3rd numbers differ - expected: '748333395', found: '713415395'