QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#729328#9566. Topologyucup-team3931#WA 2ms6140kbC++142.2kb2024-11-09 16:54:162024-11-09 16:54:17

Judging History

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

  • [2024-11-09 16:54:17]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:6140kb
  • [2024-11-09 16:54:16]
  • 提交

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 f[maxn][maxn], 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;
	}
	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;
		for (int j = i; j; j = fa[j], o = mod - o) {
			ll k = 1;
			if (j != i) {
				k = g[j] * h[i] % mod * sz[j] % mod * inv[sz[j] - sz[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 * k) % 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: 4044kb

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

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

input:

2
1

output:

1 1

result:

ok 2 number(s): "1 1"

Test #4:

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

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 97121343 309923082 207037361 365818778 480822314 460733893 60221893 893837140 117425146 939089597 708088233 581563181 64972505 308804092 895029395 144896249 969434435 364527291 433425931 153372142 528036358 987874686 511008942 839080036 831374474 740284852 359120858 329...

result:

wrong answer 4th numbers differ - expected: '201481008', found: '97121343'