QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#729383#9566. Topologyucup-team3931#WA 2ms4096kbC++142.3kb2024-11-09 17:01:212024-11-09 17:01:30

Judging History

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

  • [2024-11-09 17:01:30]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4096kb
  • [2024-11-09 17:01:21]
  • 提交

answer

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define uint unsigned
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 5050;
const ll mod = 998244353;

inline ll qpow(ll b, ll p) {
	ll res = 1;
	while (p) {
		if (p & 1) {
			res = res * b % mod;
		}
		b = b * b % mod;
		p >>= 1;
	}
	return res;
}

ll n, fac[maxn], ifac[maxn], inv[maxn], a[maxn], fa[maxn];
vector<int> G[maxn];

inline ll C(ll n, ll m) {
	if (n < m || n < 0 || m < 0) {
		return 0;
	} else {
		return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
	}
}

ll sz[maxn], g[maxn], h[maxn];

void dfs(int u) {
	sz[u] = 1;
	g[u] = h[u] = 1;
	for (int v : G[u]) {
		dfs(v);
		sz[u] += sz[v];
		g[u] = g[u] * g[v] % mod;
		h[u] = h[u] * h[v] % mod;
	}
	g[u] = g[u] * inv[sz[u]] % mod;
	h[u] = h[u] * sz[u] % mod;
}

ll K, U;

int dfs2(int u) {
	if (u == U) {
		return 0;
	}
	int s = 1;
	for (int v : G[u]) {
		int t = dfs2(v);
		s += t;
	}
	K = K * inv[s] % mod;
	return s;
}

void solve() {
	scanf("%lld", &n);
	for (int i = 2, p; i <= n; ++i) {
		scanf("%d", &p);
		G[p].pb(i);
		fa[i] = p;
	}
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) {
		fac[i] = fac[i - 1] * i % mod;
	}
	ifac[n] = qpow(fac[n], mod - 2);
	for (int i = n - 1; ~i; --i) {
		ifac[i] = ifac[i + 1] * (i + 1) % mod;
	}
	inv[1] = 1;
	for (int i = 2; i <= n; ++i) {
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
	}
	dfs(1);
	for (int i = 1; i <= n; ++i) {
		K = 1;
		U = i;
		dfs2(1);
		a[i] = fac[n - sz[i]] * K % mod;
	}
	for (int i = 1; i <= n; ++i) {
		ll ans = 0, o = 1, k = 1;
		for (int j = i; j; j = fa[j], o = mod - o) {
			if (j != i) {
				k = k * sz[j] % mod * inv[sz[j] - sz[i]] % mod;
			}
			ll t = k * g[j] % mod * h[i] % mod * fac[sz[j] - sz[i]] % mod;
			ans = (ans + o * C(n - sz[j] - i + sz[j], sz[j] - 1) % mod * a[j] % mod * C(sz[j] - 1, sz[i] - 1) % mod * t) % mod;
		}
		printf("%lld%c", ans * g[i] % mod * fac[sz[i]] % mod, " \n"[i == n]);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4052kb

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: 3912kb

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: 3960kb

input:

2
1

output:

1 1

result:

ok 2 number(s): "1 1"

Test #4:

score: -100
Wrong Answer
time: 2ms
memory: 4096kb

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 205460904 326768585 197453895 12205680 151789927 302161323 583389352 677987739 790299927 271511598 996416931 309831010 742008004 785223973 734952162 171955885 789706642 338413991 874723211 372921049 232740746 890852610 348518273 118801029 869886 9325...

result:

wrong answer 6th numbers differ - expected: '934007150', found: '205460904'