QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#300447#7792. Tree Topological Order Countingzyc0704190 0ms0kbC++142.4kb2024-01-08 11:47:402024-01-08 11:47:40

Judging History

你现在查看的是最新测评结果

  • [2024-01-08 11:47:40]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-01-08 11:47:40]
  • 提交

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];

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() {
    freopen("in.in", "r", stdin);
    freopen("mine.out", "w", stdout);
    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;
        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 * iC(sz[fa[i]] - 1, sz[i]) % mod;
                res = 1ll * res * iC(n - k, sz[fa[i]] - 1) % mod;
                res = 1ll * res * C(n - k - sz[i], sz[fa[i]] - sz[i] - 1) % mod;
                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: 0
Dangerous Syscalls

Test #1:

score: 0
Dangerous Syscalls

input:

10
1 2 2 4 2 5 3 2 3
421487749 899442061 973943239 478653728 122912827 681073947 761973567 862016787 295035337 313094543

output:


result:


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
Dangerous Syscalls

Test #22:

score: 0
Dangerous Syscalls

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%