QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#744264 | #9566. Topology | Deltax | WA | 1ms | 12908kb | C++14 | 2.1kb | 2024-11-13 21:23:03 | 2024-11-13 21:23:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
typedef pair <int, int> pii;
inline int read() {
int x = 0, f = 0;
char c = getchar();
while (!isdigit(c)) {if (c == '-') f = 1; c = getchar();}
while (isdigit(c)) x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f? -x : x;
}
const int MAXN = 5000;
const int Mod = 998244353;
vector <int> G[MAXN + 10];
int f[MAXN + 10], siz[MAXN + 10];
int dp[MAXN + 10][MAXN + 10], g[MAXN + 10];
int fac[MAXN + 10], ifac[MAXN + 10];
inline int fastpow(int x, int p) {
int ans = 1;
while (p) {
if (p & 1) ans = 1ll * ans * x % Mod;
x = 1ll * x * x % Mod;
p >>= 1;
}
return ans;
}
inline int C(int n, int m) {
if (n < m || n < 0 || m < 0) return 0;
return 1ll * fac[n] * ifac[m] % Mod * ifac[n - m] % Mod;
}
void dfs(int x) {
g[x] = 1;
for (auto v : G[x]) {
dfs(v);
siz[x] += siz[v];
g[x] = 1ll * g[x] * g[v] % Mod * C(siz[x], siz[v]) % Mod;
}
++siz[x];
}
int n;
void DP(int x) {
int prod = 1;
for (auto v : G[x])
prod = 1ll * prod * g[v] % Mod;
for (auto v : G[x]) {
int val = 1ll * prod * fastpow(g[v], Mod - 2) % Mod;
int sum = 0;
for (int j = 1; j <= n - siz[v] + 1; ++j) {
dp[v][j] = (dp[v][j - 1] + 1ll * dp[x][j - 1] * C(n - siz[v] - (j - 1), siz[x] - siz[v] - 1)) % Mod;
}
for (int j = 1; j <= n - siz[v] + 1; ++j)
dp[v][j] = 1ll * dp[v][j] * val % Mod;
DP(v);
}
}
signed main() {
// freopen ("std.in", "r", stdin);
// freopen ("std.out", "w", stdout);
n = read();
for (int i = 2; i <= n; ++i) {
f[i] = read();
G[f[i]].pb(i);
}
fac[0] = 1;
for (int i = 1; i <= n; ++i)
fac[i] = 1ll * fac[i - 1] * i % Mod;
ifac[n] = fastpow(fac[n], Mod - 2);
for (int i = n - 1; i >= 0; --i)
ifac[i] = 1ll * ifac[i + 1] * (i + 1) % Mod;
dp[1][1] = 1;
dfs(1);
DP(1);
//cerr << C(4, 2) << endl;
for (int i = 1; i <= n; ++i)
printf("%lld ", 1ll * dp[i][i] * C(n - i, siz[i] - 1) % Mod * g[i] % Mod);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4004kb
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: 3960kb
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: 4032kb
input:
2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 7892kb
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 934007150 548415590 60830816 948776140 565765713 126668425 603509050 491206892 433369091 271511598 706737964 70425819 69672788 713120782 734952162 267434947 720007515 670449595 828144080 372921049 434477621 877300187 307269573 636190001 793011806 327...
result:
ok 500 numbers
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 12908kb
input:
500 1 2 3 4 5 2 6 8 9 10 11 12 13 14 15 16 7 18 19 17 21 20 22 24 25 26 23 27 29 30 2 28 31 34 35 36 37 38 39 33 40 42 41 43 45 46 17 47 49 35 50 52 44 53 9 55 54 57 58 59 61 60 62 64 65 66 67 68 69 70 63 71 27 73 25 70 75 78 79 80 75 80 81 84 72 86 87 85 89 90 91 88 92 16 71 93 53 94 99 10 100 12 9...
output:
199957339 199957339 713415395 633706456 352131089 624197058 360461813 532766543 643300762 951160691 515628617 162173363 188718163 899871076 591019765 913659763 516547362 997687530 555134171 277981670 434565875 428443692 950912211 201268221 799265651 31491534 581175237 513698743 795109450 730574236 6...
result:
wrong answer 3rd numbers differ - expected: '748333395', found: '713415395'