QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#749712 | #9566. Topology | fosov | TL | 1ms | 3892kb | C++14 | 2.4kb | 2024-11-15 09:33:26 | 2024-11-15 09:33:27 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define lll __int128
#define INF 0x3f3f3f3f
#define LNF 0x3f3f3f3f3f3f3f3fll
#define MOD 998244353
#define pii pair<int, int>
#define N 5050
struct mint {
ll v;
mint() {};
mint(ll v): v(v%MOD) {};
mint operator+ (mint x) {
return v + x.v;
}
mint operator- (mint x) {
return v - x.v + MOD;
}
mint operator* (mint x) {
return v * x.v;
}
mint operator/ (mint x) {
return *this * x.pow(MOD-2);
}
mint pow(ll p) {
if (p == 0) return 1;
if (p == 1) return *this;
return (*this**this).pow(p/2) * pow(p&1);
}
};
mint fac[N], inv[N];
void init() {
fac[0] = 1;
for (int i = 1; i < N; ++ i) fac[i] = fac[i-1] * i;
inv[N-1] = mint(1) / fac[N-1];
for (int i = N-2; i >= 0; -- i) inv[i] = inv[i+1] * (i+1);
}
mint nCr(int n, int r) {
if (n < r) return 0;
return fac[n] * inv[n-r] * inv[r];
}
int n;
vector<int> G[N];
int sz[N];
mint ms[N], top[N], f[N][N], p[N];
void dfs(int u, int fa) {
sz[u] = 1;
ms[u] = 1;
top[u] = 1;
for (auto v : G[u]) {
if (v == fa) continue;
dfs(v, u);
sz[u] = sz[u] + sz[v];
ms[u] = ms[u] * ms[v];
top[u] = top[u] * inv[sz[v]] * top[v];
}
ms[u] = ms[u] * sz[u];
top[u] = top[u] * fac[sz[u] - 1];
assert(top[u].v == (fac[sz[u]] / ms[u]).v);
}
void dfs1(int u, int fa) {
if (fa == 0) {
for (int i = 1; i <= n; ++ i) f[u][i] = i == 1 ? top[u] : 0;
} else {
for (int i = 1; i <= n; ++ i) {
f[u][i] = 0;
for (int j = 1; j < i; ++ j) {
if (f[fa][j].v == 0) continue;
f[u][i] = f[u][i] + f[fa][j] / nCr(n - j, sz[u]);
}
f[u][i] = f[u][i] * nCr(n - i, sz[u] - 1);
}
}
for (auto v : G[u]) {
if (v == fa) continue;
dfs1(v, u);
}
}
int main() {
#ifdef TEST
freopen("zz.in", "r+", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
init();
cin >> n;
for (int i = 2; i <= n; ++ i) {
int f; cin >> f;
G[i].emplace_back(f);
G[f].emplace_back(i);
}
dfs(1, 0);
dfs1(1, 0);
mint res(0);
for (int i = 1; i <= n; ++ i) cout << (f[i][i]).v << ' ';
cout << '\n';
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3820kb
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: 1ms
memory: 3832kb
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: 1ms
memory: 3892kb
input:
2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #4:
score: -100
Time Limit Exceeded
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...