QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#829995#9576. Ordainer of Inexorable JudgmentDiaoTianhaoWA 0ms3888kbC++171.6kb2024-12-24 15:22:072024-12-24 15:22:15

Judging History

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

  • [2024-12-24 15:22:15]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3888kb
  • [2024-12-24 15:22:07]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
int n;
vector<int>g[5010], f(5010), cnt(5010);
vector<long long>fac(5010), inv(5010), mul(5010);
long long dp[5010][5010];
long long fastpower(long long a, long long b) {
	long long ans = 1;
	while(b) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
		b /= 2;
	}
	return ans;
}
long long C(int n, int m) {
	if(n < m) return 0;
	return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
void dfs(int now) {
	cnt[now] = 1;
	for(auto v : g[now]) {
		dfs(v);
		cnt[now] += cnt[v];
	}
	f[now] = fac[cnt[now]];
	mul[now] = cnt[now];
	for(auto v : g[now]) {
		mul[now] = mul[now] * mul[v] % mod;
	}
	f[now] = f[now] * fastpower(mul[now], mod - 2) % mod;
}
void dfs1(int now) {
	for(auto v : g[now]) {
		long long tmp = f[now] * mul[v] % mod * fac[cnt[now] - cnt[v] - 1] % mod * inv[cnt[now] - 1] % mod;
		for(int i = 1; i <= n; i++) {
			dp[v][i] = dp[now][i - 1] * tmp % mod * C(n - i + 1 - cnt[v], cnt[now] - cnt[v] - 1) % mod;
			dp[v][i] = (dp[v][i] + dp[v][i - 1]) % mod;
		}
		dfs1(v);
	}
}
int main() {
	fac[0] = 1;
	inv[0] = inv[1] = 1;
	for(int i = 1; i <= 5000; i++) fac[i] = fac[i - 1] * i % mod;
	for(int i = 2; i <= 5000; i++) inv[i] = inv[mod % i] * (mod - mod / i) % mod;
	for(int i = 2; i <= 5000; i++) inv[i] = inv[i] * inv[i - 1] % mod;
	cin >> n;
	for(int i = 2; i <= n; i++) {
		int v;
		cin >> v;
		g[v].push_back(i);
	}
	dp[1][1] = 1;
	dfs(1);
	dfs1(1);
	for(int i = 1; i <= n; i++) {
		cout << dp[i][i]*f[i] % mod *C(n - i, cnt[i] - 1) % mod << " ";
	}
	cout << "\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3888kb

input:

3 1 0 1 1
1 2
2 1
2 2

output:

2 1 0 

result:

wrong answer 1st numbers differ - expected: '1.0000000', found: '2.0000000', error = '1.0000000'