QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#312203 | #7792. Tree Topological Order Counting | Galex | 0 | 155ms | 62528kb | C++14 | 2.1kb | 2024-01-23 16:29:32 | 2024-01-23 16:29:33 |
Judging History
answer
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int read() {
int s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
f = (ch == '-' ? -1 : 1), ch = getchar();
while (ch >= '0' && ch <= '9')
s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * f;
}
const int MAXN = 5005, mod = 1000000007;
int qpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1)
res = (LL)res * a % mod;
a = (LL)a * a % mod, b >>= 1;
}
return res;
}
#define Fplus(x, y) (x + y < mod ? x += y : x += y - mod)
#define Fminus(x, y) (x >= y ? x -= y : x += mod - y)
int fac[MAXN], inv[MAXN];
void init(int n = 5000) {
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = (LL)fac[i - 1] * i % mod;
inv[n] = qpow(fac[n], mod - 2);
for (int i = n; i; i--)
inv[i - 1] = (LL)inv[i] * i % mod;
}
int C(int n, int m) {
return n < m ? 0 : (LL)fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int n, b[MAXN];
vector<int> e[MAXN];
int fa[MAXN], sz[MAXN];
int g[MAXN][MAXN] = {{0}}, f[MAXN] = {0};
int pre[MAXN] = {0};
signed main() {
n = read();
for (int i = 2; i <= n; i++)
e[fa[i] = read()].push_back(i);
for (int i = 1; i <= n; i++)
b[i] = read();
init();
for (int i = n; i; i--) {
sz[i] = 1, f[i] = 1;
for (int j : e[i])
sz[i] += sz[j], f[i] = (LL)f[i] * f[j] % mod;
f[i] = (LL)f[i] * qpow(sz[i], mod - 2);
}
g[1][1] = 1;
for (int i = 2; i <= n; i++) {
int cnt = sz[fa[i]] - sz[i] - 1, coef = fac[cnt];
for (int j : e[fa[i]])
if (i != j)
coef = (LL)coef * f[j] % mod;
for (int j = 1; j <= n - sz[i]; j++)
pre[j] = (pre[j - 1] + (LL)C(n - j - sz[i], cnt) * coef % mod * g[fa[i]][j] % mod) % mod;
for (int j = 1; j <= n - sz[i] + 1; j++)
g[i][j] = pre[j - 1];
}
for (int i = 1; i <= n; i++) {
int coef = fac[sz[i] - 1];
for (int j : e[i])
coef = (LL)coef * f[j] % mod;
// cout << coef << endl;
int ans = 0;
for (int j = 1; j <= n; j++)
ans = (ans + (LL)coef * C(n - j, sz[i] - 1) % mod * g[i][j] % mod * b[j] % mod) % mod;
printf("%d ", ans);
}
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: 5884kb
input:
10 1 2 2 4 2 5 3 2 3 421487749 899442061 973943239 478653728 122912827 681073947 761973567 862016787 295035337 313094543
output:
-294465409 -757804165 -651100810 844925059 320019016 -457930087 346368542 -861344729 -457930087 -861344729
result:
wrong answer 1st numbers differ - expected: '132551152', found: '-294465409'
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: 155ms
memory: 62528kb
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:
889753195 -33232893 -824965480 -607318702 532563467 -971681172 629270580 -714624489 379488371 -929094108 670176810 -847362187 412918489 -654004944 156295343 843857977 -897620850 176870023 -247013126 -707539077 773163275 445611348 386151834 761715860 -781164779 -568966391 479347929 -928041804 -671929...
result:
wrong answer 1st numbers differ - expected: '16671810', found: '889753195'
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #6:
0%