QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#312203#7792. Tree Topological Order CountingGalex0 155ms62528kbC++142.1kb2024-01-23 16:29:322024-01-23 16:29:33

Judging History

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

  • [2024-01-23 16:29:33]
  • 评测
  • 测评结果:0
  • 用时:155ms
  • 内存:62528kb
  • [2024-01-23 16:29:32]
  • 提交

answer

#include <bits/stdc++.h>
#define LL long long
using namespace std;

int read() {
	int s = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9')
		f = (ch == '-' ? -1 : 1), ch = getchar();
	while (ch >= '0' && ch <= '9')
		s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
	return s * f;
}

const int MAXN = 5005, mod = 1000000007;

int qpow(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1)
			res = (LL)res * a % mod;
		a = (LL)a * a % mod, b >>= 1;
	}
	return res;
}

#define Fplus(x, y) (x + y < mod ? x += y : x += y - mod)
#define Fminus(x, y) (x >= y ? x -= y : x += mod - y)

int fac[MAXN], inv[MAXN];

void init(int n = 5000) {
	fac[0] = 1;
	for (int i = 1; i <= n; i++)
		fac[i] = (LL)fac[i - 1] * i % mod;
	inv[n] = qpow(fac[n], mod - 2);
	for (int i = n; i; i--)
		inv[i - 1] = (LL)inv[i] * i % mod;
}

int C(int n, int m) {
	return n < m ? 0 : (LL)fac[n] * inv[m] % mod * inv[n - m] % mod;
}

int n, b[MAXN];
vector<int> e[MAXN];
int fa[MAXN], sz[MAXN];
int g[MAXN][MAXN] = {{0}}, f[MAXN] = {0};
int pre[MAXN] = {0};

signed main() {
	n = read();
	for (int i = 2; i <= n; i++)
		e[fa[i] = read()].push_back(i);
	for (int i = 1; i <= n; i++)
		b[i] = read();
	init();
	for (int i = n; i; i--) {
		sz[i] = 1, f[i] = 1;
		for (int j : e[i])
			sz[i] += sz[j], f[i] = (LL)f[i] * f[j] % mod;
		f[i] = (LL)f[i] * qpow(sz[i], mod - 2);
	}
	g[1][1] = 1;
	for (int i = 2; i <= n; i++) {
		int cnt = sz[fa[i]] - sz[i] - 1, coef = fac[cnt];
		for (int j : e[fa[i]])
			if (i != j)
				coef = (LL)coef * f[j] % mod;
		for (int j = 1; j <= n - sz[i]; j++)
			pre[j] = (pre[j - 1] + (LL)C(n - j - sz[i], cnt) * coef % mod * g[fa[i]][j] % mod) % mod;
		for (int j = 1; j <= n - sz[i] + 1; j++)
			g[i][j] = pre[j - 1];
	}
	for (int i = 1; i <= n; i++) {
		int coef = fac[sz[i] - 1];
		for (int j : e[i])
			coef = (LL)coef * f[j] % mod;
		// cout << coef << endl;
		int ans = 0;
		for (int j = 1; j <= n; j++)
			ans = (ans + (LL)coef * C(n - j, sz[i] - 1) % mod * g[i][j] % mod * b[j] % mod) % mod;
		printf("%d ", ans);
	}
	return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

input:

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

output:

-294465409 -757804165 -651100810 844925059 320019016 -457930087 346368542 -861344729 -457930087 -861344729 

result:

wrong answer 1st numbers differ - expected: '132551152', found: '-294465409'

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
Wrong Answer

Test #22:

score: 0
Wrong Answer
time: 155ms
memory: 62528kb

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:

889753195 -33232893 -824965480 -607318702 532563467 -971681172 629270580 -714624489 379488371 -929094108 670176810 -847362187 412918489 -654004944 156295343 843857977 -897620850 176870023 -247013126 -707539077 773163275 445611348 386151834 761715860 -781164779 -568966391 479347929 -928041804 -671929...

result:

wrong answer 1st numbers differ - expected: '16671810', found: '889753195'

Subtask #6:

score: 0
Skipped

Dependency #4:

0%

Subtask #7:

score: 0
Skipped

Dependency #6:

0%