QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#729279#9566. Topologyucup-team3931#WA 2ms4096kbC++142.1kb2024-11-09 16:49:362024-11-09 16:49:40

Judging History

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

  • [2024-11-09 16:49:40]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4096kb
  • [2024-11-09 16:49:36]
  • 提交

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

詳細信息

Test #1:

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

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

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

input:

2
1

output:

1 1

result:

ok 2 number(s): "1 1"

Test #4:

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

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 663155723 455887250 757632383 460217724 649304175 517775330 554258125 554226785 10167134 138075740 492641302 654740132 604887467 669211771 246522573 822630502 969434435 343161356 238193347 326848701 611904505 593728478 58405572 556112967 509189934 35743495 624144527 518...

result:

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