QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#749965#9566. TopologycaojcWA 1ms5516kbC++202.8kb2024-11-15 11:44:182024-11-15 11:44:19

Judging History

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

  • [2024-11-15 11:44:19]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5516kb
  • [2024-11-15 11:44:18]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pii pair<int, int>

#define db(args...){\
    string _s = #args; replace(_s.begin(), _s.end(), ',', ' ');\
    stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); cout << '\n';}
void err(istream_iterator<string> it){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << *it << " = " << a << ' ';
    err(++it, args...);
}

const int mod = 998244353;
const int N = 1e4 + 10;
ll fac[N], ifac[N], inv[N];
void init() {
    fac[0] = ifac[0] = ifac[1] = inv[1] = 1;
    for(int i = 1; i < N; i++) {
        fac[i] = fac[i - 1] * i % mod;
        if(i > 1) ifac[i] = (mod - mod / i) * ifac[mod % i] % mod, inv[i] = ifac[i];
    }
    for(int i = 1; i < N; i++) ifac[i] = ifac[i - 1] * ifac[i] % mod;
}
ll C(int n, int m) {
    return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
ll ksm(ll a, ll b = mod - 2) {
    ll res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod, b /= 2;
    }
    return res;
} 
void mul(ll &x, ll y) {
    x = x * y % mod;
}
void add(ll &x, ll y) {
    x += y;
    if (x >= mod) x -= mod;
}

void solve() {
    int n;
    cin >> n;

    vector e(n + 1, vector<int>());
    for (int i = 2, p; i <= n; i++) {
        cin >> p;
        e[p].push_back(i);
    }    

    vector<ll> sz(n + 1, 1), mulsz(n + 1, 1);
    auto dfs1 = [&] (auto &&self, int u, int fa)->void {
        sz[u] = 1, mulsz[u] = 1;
        for (auto v : e[u]) {
            self(self, v, u);
            sz[u] += sz[v];
            mul(mulsz[u], mulsz[v]);
        }
        mul(mulsz[u], sz[u]);
    };
    dfs1(dfs1, 1, 0);

    vector f(n + 1, vector<ll>(n + 1, 0));
    f[1][1] = 1;

    vector<ll> ans(n + 1);
    auto dfs = [&] (auto &&self, int u, int fa)->void {
        ans[u] = f[u][u] * C(n - u, sz[u] - 1) % mod * fac[sz[u]] % mod * ksm(mulsz[u]) % mod;

        for (auto v : e[u]) {
            ll puv = fac[sz[u] - sz[v]];
            ll B = mulsz[u] * ksm(mulsz[v]) % mod * ksm(sz[u]) % mod * (sz[u] - sz[v]) % mod;
            mul(puv, ksm(B));
            for (int x = 2; x <= n; x++) {
                for (int y = x - 1; y <= x - 1; y++) {
                    add(f[v][x], f[u][y] * C(n - y - sz[v], sz[u] - sz[v] - 1));
                }
                mul(f[v][x], puv);
                add(f[v][x], f[v][x - 1]);
            }
            self(self, v, u);
        }
    };
    dfs(dfs, 1, 0);
    for (int i = 1; i <= n; i++) cout << ans[i] << " \n" [i == n];
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    init();
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

/*
g++ 1.cpp -std=c++20 -o 1 && ./1 < in.txt > out.txt
 */



Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

2
1

output:

1 1

result:

ok 2 number(s): "1 1"

Test #4:

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

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 575070429 578212032 -644994296 689280130 78112040 81735938 367116937 797041563 -576623307 -665064827 -745868274 -416679245 -83014800 -119748732 -732318706 -242725625 -880059406 -459034602 -175880465 -353673175 -250160588 -132515375 -608711260 -880291...

result:

wrong answer 6th numbers differ - expected: '934007150', found: '575070429'