QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#293432#7792. Tree Topological Order Countingoscaryang0 123ms4032kbC++141.9kb2023-12-29 09:27:242023-12-29 09:27:24

Judging History

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

  • [2023-12-29 09:27:24]
  • 评测
  • 测评结果:0
  • 用时:123ms
  • 内存:4032kb
  • [2023-12-29 09:27:24]
  • 提交

answer

#include<bits/stdc++.h>

#define vc vector
#define pb emplace_back
#define pii pair<int, int>
#define mkp make_pair
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define lep(i, a, b) for(int i = (a); i >= (b); --i)

using namespace std;

inline int read() {
	int x = 0, w = 0; char ch = getchar(); while(!isdigit(ch)) w |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar(); return w ? -x : x; 
}

const int N = 5005, P = 1e9 + 7;

int fc[N], ifc[N];
inline void inc(int &x, int y) { x += y - P; x += (x >> 31) & P; }
inline int power(int a, int b) { int res = 1; for(; b; b >>= 1, a = 1ll * a * a % P) if(b & 1) res = 1ll * res * a % P; return res; }
inline void fac_init(int n) {
	fc[0] = ifc[0] = 1;
	rep(i, 1, n) fc[i] = 1ll * i * fc[i - 1] % P;
	rep(i, 1, n) ifc[i] = power(fc[i], P - 2);
}

int n, b[N], fa[N], sz[N], g[N], ans[N], f[N], s[N];
vc<int> G[N];

inline void dfs1(int x) {
	sz[x] = g[x] = 1;
	for(auto y: G[x]) {
		dfs1(y); sz[x] += sz[y];
		g[x] = 1ll * g[x] * g[y] % P;
	}
	g[x] = 1ll * g[x] * ifc[sz[x]] % P;
}

inline void presum() { rep(i, 1, n) inc(s[i] = s[i - 1], f[i - 1]); }

inline void dfs2(int x) {
	presum(); 
	int val = 1ll * g[x] * fc[sz[x]] % P;
	rep(i, 1, n) if(n - i >= sz[i] - 1) 
		inc(ans[x], 1ll * s[i] * b[i] % P * val % P * fc[n - i] % P * ifc[n - i - sz[x] + 1] % P);
	
	vc<int> dp(n + 1, 0);
	for(auto y: G[x]) {
		val = 1ll * g[x] * fc[sz[x]] % P * power(g[y], P - 2) % P;
		rep(i, 0, n) dp[i] = f[i]; 
		presum();
		rep(i, 0, n) 
			if(n - i >= sz[x] - 1) 
				f[i] = 1ll * s[i] * val % P * fc[n - i - sz[y]] % P * ifc[n - i - sz[x] + 1] % P;
			else f[i] = 0;
		dfs2(y);
		rep(i, 0, n) f[i] = dp[i], dp[i] = 0;
	}
}

signed main() {
	n = read();
	fac_init(n);
	rep(i, 2, n) fa[i] = read(), G[fa[i]].pb(i);
	rep(i, 1, n) b[i] = read();

	dfs1(1);
	f[0] = 1;
	dfs2(1);
	
	rep(i, 1, n) printf("%d ", ans[i]); putchar(10);
	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: 1ms
memory: 3780kb

input:

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

output:

877899487 402764406 922462533 922462533 160009508 209276052 173184271 666596893 209276052 666596893 

result:

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

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: 123ms
memory: 4032kb

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:

494259578 711435140 883176427 168154637 182796954 720535967 393905492 555973979 934559922 432345224 543838608 495651079 477034500 511819696 740783649 160035119 807717044 219235566 538516823 424939270 543524249 757062665 303175068 441227981 544008993 562368435 344919173 603531038 119698802 623396152 ...

result:

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

Subtask #6:

score: 0
Skipped

Dependency #4:

0%

Subtask #7:

score: 0
Skipped

Dependency #6:

0%