QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#300437#7792. Tree Topological Order Countingzyc0704195 1ms3916kbC++142.5kb2024-01-08 11:32:572024-01-08 11:32:57

Judging History

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

  • [2024-01-08 11:32:57]
  • 评测
  • 测评结果:5
  • 用时:1ms
  • 内存:3916kb
  • [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%