QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#729328 | #9566. Topology | ucup-team3931# | WA | 2ms | 6140kb | C++14 | 2.2kb | 2024-11-09 16:54:16 | 2024-11-09 16:54:17 |
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) {
ll k = 1;
if (j != i) {
k = g[j] * h[i] % mod * sz[j] % mod * inv[sz[j] - sz[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 * k) % 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: 4044kb
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: 6140kb
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: 6048kb
input:
2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #4:
score: -100
Wrong Answer
time: 2ms
memory: 4124kb
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 97121343 309923082 207037361 365818778 480822314 460733893 60221893 893837140 117425146 939089597 708088233 581563181 64972505 308804092 895029395 144896249 969434435 364527291 433425931 153372142 528036358 987874686 511008942 839080036 831374474 740284852 359120858 329...
result:
wrong answer 4th numbers differ - expected: '201481008', found: '97121343'