QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#293433 | #7792. Tree Topological Order Counting | oscaryang | 0 | 121ms | 4428kb | C++14 | 2.0kb | 2023-12-29 09:31:44 | 2023-12-29 09:31:45 |
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[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%