QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#300437 | #7792. Tree Topological Order Counting | zyc070419 | 5 | 1ms | 3916kb | C++14 | 2.5kb | 2024-01-08 11:32:57 | 2024-01-08 11:32:57 |
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
const int mod = 1e9 + 7;
inline int add(int x, int y) {x += y; return x >= mod ? x - mod : x;}
inline int del(int x, int y) {x -= y; return x < 0 ? x + mod : x;}
inline void Add(int &x, int y) {x = add(x, y);}
inline void Del(int &x, int y) {x = del(x, y);}
int n, fa[N], sz[N], dp[N][N], fac[N], inv[N], depth[N], INV[N], val[N], a[N], iva[N];
inline int C(int x, int y) {return (x < 0 || y < 0 || x < y) ? 0 : 1ll * fac[x] * inv[y] % mod * inv[x - y] % mod;}
inline int iC(int x, int y) {return 1ll * inv[x] * fac[y] % mod * fac[x - y] % mod;}
inline int qpow(int x, int y) {
int res = 1;
while (y) {
if (y & 1) res = 1ll * res * x % mod;
x = 1ll * x * x % mod;
y >>= 1;
}
return res;
}
int main() {
scanf("%d", &n); depth[1] = 1;
fac[0] = 1;
for (int i = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
inv[n] = qpow(fac[n], mod - 2);
for (int i = n; i >= 1; --i) inv[i - 1] = 1ll * inv[i] * i % mod;
INV[1] = 1;
for (int i = 2; i <= n; ++i) INV[i] = 1ll * (mod - mod / i) * INV[mod % i] % mod;
for (int i = 1; i <= n; ++i) val[i] = 1;
for (int i = 2; i <= n; ++i) scanf("%d", &fa[i]), depth[i] = depth[fa[i]] + 1;
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = n; i >= 1; --i) {
sz[i]++; val[i] = 1ll * val[i] * INV[sz[i]] % mod;
iva[i] = qpow(val[i], mod - 2);
sz[fa[i]] += sz[i];
val[fa[i]] = 1ll * val[fa[i]] * val[i] % mod;
val[i] = 1ll * val[i] * fac[sz[i]] % mod;
}
dp[1][1] = fac[n];
for (int i = 1; i <= n; ++i) dp[1][1] = 1ll * dp[1][1] * INV[sz[i]] % mod;
for (int i = 2; i <= n; ++i)
for (int j = depth[i]; j <= n; ++j) {
for (int k = depth[i] - 1; k < j; ++k) {
if (dp[fa[i]][k] == 0) continue;
int res = dp[fa[i]][k];
res = 1ll * res * C(n - j, sz[i] - 1) % mod * val[i] % mod;
res = 1ll * res * iC(n - k, sz[fa[i]] - 1) % mod * inv[sz[fa[i]]] % mod * sz[fa[i]] % mod * iva[i] % mod;
res = 1ll * res * fac[sz[fa[i]] - sz[i]] % mod * INV[sz[fa[i]] - sz[i]] % mod;
res = 1ll * res * C(n - k - sz[i], sz[fa[i]] - sz[i] - 1);
Add(dp[i][j], res);
}
}
for (int i = 1, res; i <= n; ++i) {
res = 0;
for (int j = 1; j <= n; ++j) Add(res, 1ll * dp[i][j] * a[j] % mod);
printf("%d%c", res, i == n ? '\n' : ' ');
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 0ms
memory: 3832kb
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: 0ms
memory: 3804kb
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: 1ms
memory: 3916kb
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 270322976 277088290 558845717 809080149 232796969 -478874574 750739527 -478874574 16998632 -743715009 16998632 294917125 922627954 922627954 750739527 294917125 294917125 750739527 294917125
result:
wrong answer 5th numbers differ - expected: '651457501', found: '809080149'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Time Limit Exceeded
Test #22:
score: 0
Time Limit Exceeded
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%