QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#814366#9566. TopologywangjunruiWA 4ms7664kbC++141.6kb2024-12-14 17:01:332024-12-14 17:01:35

Judging History

你现在查看的是最新测评结果

  • [2024-12-14 17:01:35]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:7664kb
  • [2024-12-14 17:01:33]
  • 提交

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;
}

详细

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'