QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#293433#7792. Tree Topological Order Countingoscaryang0 121ms4428kbC++142.0kb2023-12-29 09:31:442023-12-29 09:31:45

Judging History

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

  • [2023-12-29 09:31:45]
  • 评测
  • 测评结果:0
  • 用时:121ms
  • 内存:4428kb
  • [2023-12-29 09:31:44]
  • 提交

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[x] - 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() {
	//freopen("a.in", "r", stdin);
	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: 0ms
memory: 3960kb

input:

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

output:

519742889 687550639 922462533 922462533 160009508 209276052 173184271 666596893 209276052 666596893 

result:

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

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: 121ms
memory: 4428kb

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:

523874772 367883186 978912120 804954263 364466050 545579863 989766017 678183975 489127259 543589611 692153449 136397054 667590497 882619212 405811239 244415880 523749356 132922698 551607460 737445865 990071857 302457211 395875892 501511059 305821582 562368435 733140646 29730643 604305753 6817196 739...

result:

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

Subtask #6:

score: 0
Skipped

Dependency #4:

0%

Subtask #7:

score: 0
Skipped

Dependency #6:

0%