QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#729279 | #9566. Topology | ucup-team3931# | WA | 2ms | 4096kb | C++14 | 2.1kb | 2024-11-09 16:49:36 | 2024-11-09 16:49:40 |
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 f[maxn][maxn], 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;
}
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;
for (int j = i; j; j = fa[j], o = mod - o) {
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;
}
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: 3992kb
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: 4096kb
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: 4092kb
input:
2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #4:
score: -100
Wrong Answer
time: 2ms
memory: 4024kb
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 663155723 455887250 757632383 460217724 649304175 517775330 554258125 554226785 10167134 138075740 492641302 654740132 604887467 669211771 246522573 822630502 969434435 343161356 238193347 326848701 611904505 593728478 58405572 556112967 509189934 35743495 624144527 518...
result:
wrong answer 4th numbers differ - expected: '201481008', found: '663155723'