QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#522315#7792. Tree Topological Order Countingzlt0 0ms4692kbC++142.4kb2024-08-16 21:18:352024-08-16 21:18:35

Judging History

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

  • [2024-08-16 21:18:35]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:4692kb
  • [2024-08-16 21:18:35]
  • 提交

answer

// Problem: P10013 [集训队互测 2023] Tree Topological Order Counting
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10013
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#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 = 310;
const ll mod = 1000000007;

ll n, a[maxn], fac[maxn], inv[maxn], fa[maxn], ifac[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], sz[maxn];
int st[maxn], ed[maxn], tim;

void dfs(int u) {
	sz[u] = f[u] = 1;
	st[u] = ++tim;
	for (int v : G[u]) {
		dfs(v);
		f[u] = f[u] * f[v] % mod;
		sz[u] += sz[v];
	}
	f[u] = f[u] * inv[sz[u]] % mod;
	ed[u] = tim;
}

ll g[maxn][maxn];
bool vis[maxn];

void solve() {
	scanf("%lld", &n);
	fac[0] = ifac[0] = 1;
	for (int i = 1; i <= n; ++i) {
		fac[i] = fac[i - 1] * i % mod;
	}
	inv[1] = 1;
	for (int i = 2; i <= n; ++i) {
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
		scanf("%lld", &fa[i]);
		G[fa[i]].pb(i);
	}
	for (int i = 1; i <= n; ++i) {
		ifac[i] = ifac[i - 1] * inv[i] % mod;
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
	}
	dfs(1);
	for (int i = 1; i <= n; ++i) {
		mems(g, 0);
		mems(vis, 0);
		g[i][0] = 1;
		int x = i, cnt = 0;
		vis[i] = 1;
		while (x > 1) {
			++cnt;
			int y = fa[x];
			for (int j = 0; j < sz[x]; ++j) {
				for (int k = 1; k <= sz[y] - sz[x]; ++k) {
					g[y][j + k] = (g[y][j + k] + g[x][j] * C(j + k - 1, j) % mod * C(sz[y] - j - k - 1, sz[x] - j - 1)) % mod;
				}
			}
			x = y;
			vis[x] = 1;
		}
		ll coef = fac[n - cnt - sz[i]] * f[i] % mod * fac[sz[i]] % mod, ans = 0;
		for (int j = 1; j <= n; ++j) {
			if (!vis[j] && !(st[i] <= st[j] && st[j] <= ed[i])) {
				coef = coef * inv[sz[j]] % mod;
			}
		}
		for (int j = 0; j < n; ++j) {
			ans = (ans + g[1][j] * a[j + 1]) % mod;
		}
		ans = ans * coef % mod;
		printf("%lld%c", ans, " \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

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

input:

10
1 2 2 4 2 5 3 2 3
421487749 899442061 973943239 478653728 122912827 681073947 761973567 862016787 295035337 313094543

output:

132551152 750202542 844925059 844925059 320019016 837104208 346368542 999162667 837104208 999162667

result:

wrong answer 8th numbers differ - expected: '333193779', found: '999162667'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Runtime Error

Test #22:

score: 0
Runtime Error

input:

3000
1 1 3 1 3 6 1 5 3 2 4 9 6 7 2 7 1 1 8 1 4 17 23 2 5 24 15 12 14 28 16 32 33 16 6 1 3 12 17 31 33 19 43 3 33 7 35 42 23 15 30 12 8 21 16 38 53 8 49 56 21 25 30 54 30 14 20 10 35 28 35 55 12 50 10 1 75 76 19 22 8 82 4 68 42 9 57 68 3 67 56 8 11 23 72 68 9 62 32 20 73 39 74 56 88 61 83 78 69 29 29...

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #4:

0%

Subtask #7:

score: 0
Skipped

Dependency #6:

0%