QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#387770 | #7792. Tree Topological Order Counting | JCY_ | 5 | 124ms | 51004kb | C++14 | 2.4kb | 2024-04-12 19:51:48 | 2024-04-12 19:51:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128;
using u128 = unsigned __int128;
template <typename T>
void chkmax(T &x, const T &y) {
if (x < y) x = y;
}
template <typename T>
void chkmin(T &x, const T &y) {
if (y < x) x = y;
}
constexpr int MAXN = 5010, MOD = 1e9 + 7;
void inc(int &x, int y) {
x += y;
if (x >= MOD) x -= MOD;
}
int qpow(int x, int y) {
int ret = 1;
for (; y; y >>= 1, x = (ll)x * x % MOD)
if (y & 1) ret = (ll)ret * x % MOD;
return ret;
}
int n, fa[MAXN], sz[MAXN], wys[MAXN], iwys[MAXN], inv[MAXN], dp[MAXN][MAXN];
int fac[MAXN], ifac[MAXN], ans[MAXN], b[MAXN];
vector<int> g[MAXN];
int C(int x, int y) { return (ll)fac[x] * ifac[y] % MOD * ifac[x - y] % MOD; }
void dfs(int u, int lb) {
int rb = n - sz[u] + 1;
for (int i = lb + 1; i <= rb; ++i) inc(dp[u][i], dp[u][i - 1]);
int coef = (ll)wys[u] * sz[u] % MOD * fac[sz[u] - 1] % MOD;
for (int i = lb; i <= rb; ++i) {
ans[u] = (ans[u] + (ll)dp[u][i] * C(rb - i + sz[u] - 1, rb - i) % MOD *
coef * b[i]) %
MOD;
}
for (auto v : g[u]) {
coef = (ll)wys[u] * iwys[v] % MOD * sz[u] % MOD * fac[sz[u] - sz[v] - 1] % MOD;
for (int x = lb; x <= rb; ++x) {
dp[v][x + 1] = (ll)dp[u][x] * C(rb - x + sz[u] - sz[v] - 1, rb - x) %
MOD * coef % MOD;
}
dfs(v, lb + 1);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 2; i <= n; ++i) {
cin >> fa[i];
g[fa[i]].emplace_back(i);
}
for (int i = 1; i <= n; ++i) cin >> b[i];
fill(sz + 1, sz + n + 1, 1);
for (int i = n; i >= 2; --i) sz[fa[i]] += sz[i];
fac[0] = 1;
for (int i = 1; i <= n; ++i) fac[i] = (ll)fac[i - 1] * i % MOD;
ifac[n] = qpow(fac[n], MOD - 2);
for (int i = n - 1; i >= 0; --i) ifac[i] = (ll)ifac[i + 1] * (i + 1) % MOD;
for (int i = 1; i <= n; ++i) inv[i] = (ll)ifac[i] * fac[i - 1] % MOD;
for (int i = 1; i <= n; ++i) {
wys[i] = inv[sz[i]];
iwys[i] = sz[i];
}
for (int i = n; i >= 2; --i) {
wys[fa[i]] = (ll)wys[fa[i]] * wys[i] % MOD;
iwys[fa[i]] = (ll)iwys[fa[i]] * iwys[i] % MOD;
}
dp[1][1] = 1;
dfs(1, 1);
for (int i = 1; i <= n; ++i) cout << ans[i] << " \n"[i == n];
return 0;
}
/*
g++ C.cpp -o C -std=c++14 -O2 -Wall -Wextra -Wshadow -g
-fsanitize=address,undefined
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 1ms
memory: 3792kb
input:
10 1 2 2 4 2 5 3 2 3 421487749 899442061 973943239 478653728 122912827 681073947 761973567 862016787 295035337 313094543
output:
132551152 750202542 844925059 844925059 320019016 837104208 346368542 333193779 837104208 333193779
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
10 1 2 2 4 5 4 3 7 1 226457597 222460848 126601784 27445914 811511381 52803670 776934531 832659037 955599897 927944188
output:
802913206 192357888 80729172 288305444 609011662 689888737 609011662 673713322 689888737 479113328
result:
ok 10 numbers
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #3:
score: 0
Wrong Answer
time: 0ms
memory: 3868kb
input:
20 1 1 1 4 2 5 2 5 4 6 4 7 11 11 2 9 7 2 9 305559508 68914843 154933697 736516347 250860247 264123902 632865608 32202124 861284820 505164728 564475479 136404892 645017283 837805203 802302363 50345521 511083407 292719502 356887812 390453540
output:
4420887 788130909 277088290 329621633 157393474 42292358 346897100 706626195 346897100 468004133 556186525 468004133 982694311 614012945 614012945 706626195 982694311 982694311 706626195 982694311
result:
wrong answer 2nd numbers differ - expected: '270322976', found: '788130909'
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: 124ms
memory: 51004kb
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:
16671810 -843657953 87777176 120631638 994334708 392328975 -97702321 -361651179 70301131 -790689261 -974896336 115084367 486276080 873818471 253115929 -494099758 148672394 320815418 4052622 758818977 -970353819 -552397166 -727205520 -492913882 831628583 593172088 328309069 452848085 -202090130 -1067...
result:
wrong answer 2nd numbers differ - expected: '944499931', found: '-843657953'
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #6:
0%