QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#749965 | #9566. Topology | caojc | WA | 1ms | 5516kb | C++20 | 2.8kb | 2024-11-15 11:44:18 | 2024-11-15 11:44:19 |
Judging History
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'