QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#814366 | #9566. Topology | wangjunrui | WA | 4ms | 7664kb | C++14 | 1.6kb | 2024-12-14 17:01:33 | 2024-12-14 17:01:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5000 + 5;
constexpr int mod = 998244353;
typedef long long ll;
inline ll quickpow(ll a, int b)
{
ll res = 1;
while (b)
{
if (b & 1)
(res *= a) %= mod;
(a *= a) %= mod;
b >>= 1;
}
return res;
}
int n;
ll fac[N], ifac[N];
inline ll C(int _n, int _m)
{
if (_m < 0 || _n < _m)
return 0;
return fac[_n] * ifac[_m] % mod * ifac[_n - _m] % mod;
}
vector<int> G[N];
int sze[N];
ll f[N];
inline void dfs1(int u)
{
f[u] = 1;
for (int v : G[u])
{
dfs1(v);
sze[u] += sze[v];
(f[u] *= f[v] * C(sze[u], sze[v]) % mod) %= mod;
}
++sze[u];
}
ll g[N][N];
inline void dfs2(int u)
{
for (int v : G[u])
{
ll sum = 0;
ll times = f[u] * quickpow(f[v] * C(sze[u] - 1, sze[v]) % mod, mod - 2);
for (int i = 1; i <= n; ++i)
{
(sum += g[u][i - 1] * C(n - i + 1 - sze[v], sze[u] - sze[v] - 1)) %= mod;
(g[v][i] += sum * times) %= mod;
}
dfs2(v);
}
}
inline void _main()
{
cin >> n;
for (int i = 2; i <= n; ++i)
{
int _fa;
cin >> _fa;
G[_fa].push_back(i);
}
fac[0] = 1;
for (int i = 1; i <= n; ++i)
fac[i] = fac[i - 1] * i % mod;
ifac[n] = quickpow(fac[n], mod - 2);
for (int i = n; i >= 1; --i)
ifac[i - 1] = ifac[i] * i % mod;
dfs1(1);
g[1][1] = 1;
dfs2(1);
for (int i = 1; i <= n; ++i)
cout << g[i][i] * f[i] % mod * C(n - i, sze[i] - 1) % mod << ' ';
cout << '\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int test = 1;
while (test--)
_main();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3708kb
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: 5780kb
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: 3700kb
input:
2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #4:
score: -100
Wrong Answer
time: 4ms
memory: 7664kb
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 555543055 -333576599 -870571915 732041994 -943853045 -110141613 -986162496 82951939 523375716 -829047593 -16292479 212911964 -511509920 -602491675 2317947 243395491 -72698327 584981349 515386393 -155664190 429154683 -729272571 -337052019 83442839 -677602162 -5...
result:
wrong answer 5th numbers differ - expected: '579367731', found: '555543055'