QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#732505 | #9566. Topology | quark404# | WA | 4ms | 7740kb | C++20 | 3.2kb | 2024-11-10 14:55:08 | 2024-11-10 14:55:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e3 + 10;
vector<int> e[maxn];
const int mod = 998244353;
int ans[maxn];
int g[maxn];
int f[maxn][maxn];
int sz[maxn];
int n;
int fact[maxn], invfact[maxn];
void sz_dfs(int u, int fa)
{
sz[u] = 1;
for (auto x : e[u])
{
sz_dfs(x, u);
sz[u] += sz[x];
}
}
int qpow(int x, int y)
{
int res = 1;
while (y)
{
if (y & 1)
{
res = res * x % mod;
}
x = x * x % mod;
y >>= 1;
}
return res;
}
void init()
{
fact[1] = invfact[1] = fact[0] = invfact[0] = 1;
for (int i = 2; i < maxn; i++)
{
fact[i] = fact[i - 1] * i % mod;
}
invfact[maxn - 1] = qpow(fact[maxn - 1], mod - 2);
for (int i = maxn - 2; i; i--)
{
invfact[i] = invfact[i + 1] * (i + 1) % mod;
}
}
int C(int x, int y)
{
if (x < y)
return 0;
else
{
return fact[x] * invfact[y] % mod * invfact[x - y] % mod;
}
}
void g_dfs(int u, int fa)
{
g[u] = 1;
int tot = sz[u] - 1;
for (auto x : e[u])
{
g_dfs(x, u);
g[u] = g[u] * C(tot, sz[x]) % mod * g[x] % mod;
tot -= sz[x];
}
}
int find(int k, int n1) // k个位子,放n1个元素
{
return C(k + n1 - 1, k - 1);
}
void dfs(int u, int fa)
{
int tot = 1;
// tot 代表将所有e[u].size()儿子中元素排序
for (auto x : e[u])
{
assert(C(sz[u] - 1, sz[x]) != 0);
assert(g[x] != 0);
int g2 = g[u] * qpow(C(sz[u] - 1, sz[x]), mod - 2) % mod * qpow(g[x], mod - 2) % mod;
// cout << x << ' ' << u << ' ' << g2 << endl;
int len = n - sz[u] + 1;
// cout << len << endl;
for (int y_fa = 1; y_fa <= n; y_fa++)
{ // f[1][1]
if (len < y_fa)
break;
//
int left_len = len - y_fa + 1;
// cout << left_len << endl;
// f[u][y_fa]转移
int val = f[u][y_fa] * find(left_len, sz[u] - 1 - sz[x]) * g2 % mod;
// cout << val << ?endl;
f[x][y_fa + 1] += val;
// for (int y = y_fa + 1; y <= n; y++)
// {
// f[x][y] += val;
// }
f[x][y_fa + 1] %= mod;
}
for (int y = 1; y <= n; y++)
{
f[x][y] += f[x][y - 1];
f[x][y] %= mod;
}
dfs(x, u);
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
init();
for (int i = 2; i <= n; i++)
{
int x;
cin >> x;
e[x].push_back(i);
}
sz_dfs(1, 0);
g_dfs(1, 0);
f[1][1] = 1;
dfs(1, 0);
// cout << f[2][2] << endl;
// cout << g[1] << ' ';
for (int i = 1; i <= n; i++)
{
int v = f[i][i];
// son:
// int len = n - sz[i] + 1;
// n-sz[i]
int totlen = n - sz[i] + 1 - i + 1;
// cout << find(n - sz[i], sz[i] - 1) << endl;
v = v * find(totlen, sz[i] - 1) % mod * g[i] % mod;
cout << v << ' ';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3688kb
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: 3652kb
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: 3768kb
input:
2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #4:
score: -100
Wrong Answer
time: 4ms
memory: 7740kb
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 575070429 578212032 -644994296 689280130 78112040 81735938 302063994 432198372 -179227127 -544695592 -160268776 948217021 980258217 76088385 476130387 -906884017 -98589587 911777773 -507808877 574191638 -471421285 57235577 813753949 254503182 -438496...
result:
wrong answer 6th numbers differ - expected: '934007150', found: '575070429'