QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #735707 | #9566. Topology | ucup-team4479 | WA | 1ms | 14416kb | C++23 | 2.2kb | 2024-11-11 21:21:30 | 2024-11-11 21:21:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 5005, mod = 998244353;
int fa[N], siz[N], prod[N], invp[N], fac[N], inv[N];
int g[N][N], dep[N], n, pre[N];
vector <int> E[N];
int power(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = 1ll * res * a % mod;
a = 1ll * a * a % mod, b >>= 1;
}
return res;
}
int C(int n, int m) {
return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
void dfs(int u) {
siz[u] = prod[u] = 1;
dep[u] = dep[fa[u]] + 1;
for (int v : E[u]) {
dfs(v);
siz[u] += siz[v];
prod[u] = 1ll * prod[u] * prod[v] % mod;
}
prod[u] = 1ll * prod[u] * siz[u] % mod;
invp[u] = power(prod[u], mod - 2);
}
void dp(int u) {
pre[dep[u] - 1] = 0;
for (int v : E[u]) {
int tmp = 1ll * fac[siz[u] - siz[v]] % mod * invp[u] % mod * prod[v] % mod * siz[u] % mod * power(siz[u] - siz[v], mod - 2) % mod;
for (int x = dep[u]; x <= n - siz[u] + 1; ++x) {
// if (!g[u][x]) continue;
pre[x] = (pre[x - 1] + 1ll * C(n - siz[v] - x, siz[u] - siz[v] - 1) * tmp * g[u][x]) % mod;
}
for (int x = n - siz[u] + 2; x <= n - siz[v] + 1; ++x) pre[x] = pre[x - 1];
for (int y = dep[v]; y <= n - siz[v] + 1; ++y) {
g[v][y] = pre[y - 1];
}
dp(v);
}
}
int main() {
cin.tie(nullptr) -> ios::sync_with_stdio(false);
cout.tie(0);
cin >> n;
for (int i = 2; i <= n; ++i) {
cin >> fa[i];
E[fa[i]].push_back(i);
}
fac[0] = 1;
for (int i = 1; i <= n; ++i)
fac[i] = 1ll * fac[i - 1] * i % mod;
inv[n] = power(fac[n], mod - 2);
for (int i = n; i >= 1; --i)
inv[i - 1] = 1ll * inv[i] * i % mod;
dfs(1);
g[1][1] = 1;
dp(1);
// for (int i = 1; i <= n; ++i)
// for (int j = dep[i]; j <= n - siz[i] + 1; ++j)
// printf("g[%d][%d] = %d\n", i, j, g[i][j]);
for (int i = 1; i <= n; ++i) {
int res = 1ll * g[i][i] * C(n - i, siz[i] - 1) % mod * fac[siz[i]] % mod * invp[i] % mod;
cout << res << endl;
}
return 0;
}
/*
4
1 1 2
9
1 1 2 2 3 3 4 5
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3712kb
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: 3784kb
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: 0ms
memory: 3636kb
input:
2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 14416kb
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 297560786 988440570 -529771359 -851637711 -24357130 912812324 -544695592 569943533 753509024 -386783553 870062245 476130387 574032872 697637425 180672250 834399004 -424052715 -177280223 780357473 -402228547 643417103 61...
result:
wrong answer 6th numbers differ - expected: '934007150', found: '575070429'