QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#522315 | #7792. Tree Topological Order Counting | zlt | 0 | 0ms | 4692kb | C++14 | 2.4kb | 2024-08-16 21:18:35 | 2024-08-16 21:18:35 |
answer
// Problem: P10013 [集训队互测 2023] Tree Topological Order Counting
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10013
// Memory Limit: 512 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 310;
const ll mod = 1000000007;
ll n, a[maxn], fac[maxn], inv[maxn], fa[maxn], ifac[maxn];
vector<int> G[maxn];
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
ll f[maxn], sz[maxn];
int st[maxn], ed[maxn], tim;
void dfs(int u) {
sz[u] = f[u] = 1;
st[u] = ++tim;
for (int v : G[u]) {
dfs(v);
f[u] = f[u] * f[v] % mod;
sz[u] += sz[v];
}
f[u] = f[u] * inv[sz[u]] % mod;
ed[u] = tim;
}
ll g[maxn][maxn];
bool vis[maxn];
void solve() {
scanf("%lld", &n);
fac[0] = ifac[0] = 1;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
scanf("%lld", &fa[i]);
G[fa[i]].pb(i);
}
for (int i = 1; i <= n; ++i) {
ifac[i] = ifac[i - 1] * inv[i] % mod;
}
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
dfs(1);
for (int i = 1; i <= n; ++i) {
mems(g, 0);
mems(vis, 0);
g[i][0] = 1;
int x = i, cnt = 0;
vis[i] = 1;
while (x > 1) {
++cnt;
int y = fa[x];
for (int j = 0; j < sz[x]; ++j) {
for (int k = 1; k <= sz[y] - sz[x]; ++k) {
g[y][j + k] = (g[y][j + k] + g[x][j] * C(j + k - 1, j) % mod * C(sz[y] - j - k - 1, sz[x] - j - 1)) % mod;
}
}
x = y;
vis[x] = 1;
}
ll coef = fac[n - cnt - sz[i]] * f[i] % mod * fac[sz[i]] % mod, ans = 0;
for (int j = 1; j <= n; ++j) {
if (!vis[j] && !(st[i] <= st[j] && st[j] <= ed[i])) {
coef = coef * inv[sz[j]] % mod;
}
}
for (int j = 0; j < n; ++j) {
ans = (ans + g[1][j] * a[j + 1]) % mod;
}
ans = ans * coef % mod;
printf("%lld%c", ans, " \n"[i == n]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
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: 4692kb
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 999162667 837104208 999162667
result:
wrong answer 8th numbers differ - expected: '333193779', found: '999162667'
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
Runtime Error
Test #22:
score: 0
Runtime Error
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:
result:
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #6:
0%