QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#729383 | #9566. Topology | ucup-team3931# | WA | 2ms | 4096kb | C++14 | 2.3kb | 2024-11-09 17:01:21 | 2024-11-09 17:01:30 |
Judging History
answer
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define uint unsigned
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 5050;
const ll mod = 998244353;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, fac[maxn], ifac[maxn], inv[maxn], a[maxn], fa[maxn];
vector<int> G[maxn];
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
ll sz[maxn], g[maxn], h[maxn];
void dfs(int u) {
sz[u] = 1;
g[u] = h[u] = 1;
for (int v : G[u]) {
dfs(v);
sz[u] += sz[v];
g[u] = g[u] * g[v] % mod;
h[u] = h[u] * h[v] % mod;
}
g[u] = g[u] * inv[sz[u]] % mod;
h[u] = h[u] * sz[u] % mod;
}
ll K, U;
int dfs2(int u) {
if (u == U) {
return 0;
}
int s = 1;
for (int v : G[u]) {
int t = dfs2(v);
s += t;
}
K = K * inv[s] % mod;
return s;
}
void solve() {
scanf("%lld", &n);
for (int i = 2, p; i <= n; ++i) {
scanf("%d", &p);
G[p].pb(i);
fa[i] = p;
}
fac[0] = 1;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
ifac[n] = qpow(fac[n], mod - 2);
for (int i = n - 1; ~i; --i) {
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
dfs(1);
for (int i = 1; i <= n; ++i) {
K = 1;
U = i;
dfs2(1);
a[i] = fac[n - sz[i]] * K % mod;
}
for (int i = 1; i <= n; ++i) {
ll ans = 0, o = 1, k = 1;
for (int j = i; j; j = fa[j], o = mod - o) {
if (j != i) {
k = k * sz[j] % mod * inv[sz[j] - sz[i]] % mod;
}
ll t = k * g[j] % mod * h[i] % mod * fac[sz[j] - sz[i]] % mod;
ans = (ans + o * C(n - sz[j] - i + sz[j], sz[j] - 1) % mod * a[j] % mod * C(sz[j] - 1, sz[i] - 1) % mod * t) % mod;
}
printf("%lld%c", ans * g[i] % mod * fac[sz[i]] % mod, " \n"[i == n]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4052kb
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: 3912kb
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: 3960kb
input:
2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #4:
score: -100
Wrong Answer
time: 2ms
memory: 4096kb
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 205460904 326768585 197453895 12205680 151789927 302161323 583389352 677987739 790299927 271511598 996416931 309831010 742008004 785223973 734952162 171955885 789706642 338413991 874723211 372921049 232740746 890852610 348518273 118801029 869886 9325...
result:
wrong answer 6th numbers differ - expected: '934007150', found: '205460904'