QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#749712#9566. TopologyfosovTL 1ms3892kbC++142.4kb2024-11-15 09:33:262024-11-15 09:33:27

Judging History

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

  • [2024-11-15 09:33:27]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3892kb
  • [2024-11-15 09:33:26]
  • 提交

answer

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

#define ll long long 
#define lll __int128
#define INF 0x3f3f3f3f
#define LNF 0x3f3f3f3f3f3f3f3fll
#define MOD 998244353
#define pii pair<int, int>

#define N 5050 

struct mint {
    ll v;
    mint() {};
    mint(ll v): v(v%MOD) {};

    mint operator+ (mint x) {
        return v + x.v;
    }
    mint operator- (mint x) {
        return v - x.v + MOD;
    }
    mint operator* (mint x) {
        return v * x.v;
    }
    mint operator/ (mint x) {
        return *this * x.pow(MOD-2); 
    }
    mint pow(ll p) {
        if (p == 0) return 1;
        if (p == 1) return *this;
        return (*this**this).pow(p/2) * pow(p&1);
    }
};

mint fac[N], inv[N];
void init() {
    fac[0] = 1;
    for (int i = 1; i < N; ++ i) fac[i] = fac[i-1] * i;
    inv[N-1] = mint(1) / fac[N-1];
    for (int i = N-2; i >= 0; -- i) inv[i] = inv[i+1] * (i+1);
}
mint nCr(int n, int r) {
    if (n < r) return 0;
    return fac[n] * inv[n-r] * inv[r];
}

int n;
vector<int> G[N];
int sz[N];
mint ms[N], top[N], f[N][N], p[N];

void dfs(int u, int fa) {
    sz[u] = 1;
    ms[u] = 1;
    top[u] = 1;
    for (auto v : G[u]) {
        if (v == fa) continue;
        dfs(v, u);
        sz[u] = sz[u] + sz[v];
        ms[u] = ms[u] * ms[v];
        top[u] = top[u] * inv[sz[v]] * top[v];
    }
    ms[u] = ms[u] * sz[u];
    top[u] = top[u] * fac[sz[u] - 1];
    assert(top[u].v == (fac[sz[u]] / ms[u]).v);
}

void dfs1(int u, int fa) {
    if (fa == 0) {
        for (int i = 1; i <= n; ++ i) f[u][i] = i == 1 ? top[u] : 0;
    } else {
        for (int i = 1; i <= n; ++ i) {
            f[u][i] = 0;
            for (int j = 1; j < i; ++ j) {
                if (f[fa][j].v == 0) continue;
                f[u][i] = f[u][i] + f[fa][j] / nCr(n - j, sz[u]); 
            }
            f[u][i] = f[u][i] * nCr(n - i, sz[u] - 1); 
        }
    }

    for (auto v : G[u]) {
        if (v == fa) continue;
        dfs1(v, u);
    }
}

int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    init();

    cin >> n;
    for (int i = 2; i <= n; ++ i) {
        int f; cin >> f;
        G[i].emplace_back(f);
        G[f].emplace_back(i);
    }

    dfs(1, 0);
    dfs1(1, 0);

    mint res(0);
    for (int i = 1; i <= n; ++ i) cout << (f[i][i]).v << ' ';
    cout << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3820kb

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

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

input:

2
1

output:

1 1 

result:

ok 2 number(s): "1 1"

Test #4:

score: -100
Time Limit Exceeded

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:


result: