QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#293432 | #7792. Tree Topological Order Counting | oscaryang | 0 | 123ms | 4032kb | C++14 | 1.9kb | 2023-12-29 09:27:24 | 2023-12-29 09:27:24 |
Judging History
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%