QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#261318#7792. Tree Topological Order CountingFroranzen0 2ms9680kbC++233.5kb2023-11-22 20:16:412023-11-22 20:16:44

Judging History

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

  • [2023-11-22 20:16:44]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:9680kb
  • [2023-11-22 20:16:41]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i, f, t) for(int i(f); i <= t; ++i)
#define re(i, t) for(int i(1); i <= t; ++i)
#define per(i, t, f) for(int i(t); i >= f; --i)
#define pe(i, t) for(int i(t); i >= 1; --i)
#define nx(i, u) for(int i(head[u]); i; i = e[i].nxt)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
// #define int long long
using namespace std;
typedef pair <int, int> pii;
#define pb push_back
#define fi first
#define se second
#define ix(l, r) ((l + r) | (l != r))
#define ls (ix(l, mid))
#define rs (ix(mid + 1, r))
#define mp(i, j) (make_pair(i, j))
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define eps 1e-10
#define look_memory cerr<<abs(&sT-&eD)/1024.0/1024<<'\n'
bool sT;


namespace IO {
char buf[1 << 21], *p1 = buf, *p2 = buf, buf1[1 << 21];
inline char gc() {
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}

#ifndef ONLINE_JUDGE
#endif

// #define gc getchar

template<class I>
inline void read(I &x) {
    x = 0;
    I f = 1;
    char c = gc();
    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;
        c = gc();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = gc();
    }
    x *= f;
}

template<class I>
inline void write(I x) {
    if (x == 0) {
        putchar('0');
        return;
    }
    I tmp = x > 0 ? x : -x;
    if (x < 0)
        putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        buf1[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0)
        putchar(buf1[--cnt]);
}

#define in(x) read(x)
#define outn(x) write(x), putchar('\n')
#define out(x) write(x), putchar(' ')

} using namespace IO; 

const int mod = 998244353;
const int N = 5e3 + 5;
int n, fath[N], b[N]; 
int fac[N], inv[N];
vector<int>G[N];

inline int ksm (int a, int b) {
    ll ans = 1, base = a;
    while(b) {
        if(b & 1) ans = ans * base % mod;
        base= base * base % mod;
        b >>= 1;
    }
    return ans;
}

inline int C (int n, int m) {
    if(n < 0 || m < 0 || n < m) return 0;
    return 1ll * fac[n] * inv[m] % mod * inv[n-m] % mod;
}

int rt;
int f[N][N], siz[N], g[N];

int dfs (int u) {
    f[u][0] = 1; 
    re(i, n) f[u][i] = 0;
    f[u][1] = 1;
    siz[u] = 1;
    int flg = 0;
    for(int v : G[u]) { 
        int w = dfs(v);
        flg |= w;
        f[u][0] = 1ll * f[u][0] * f[v][0] % mod * inv[siz[v]] % mod;
        re(i, siz[u]) g[i] = f[u][i], f[u][i] = 0;
        re(i, siz[u]) {
            rep(j, 0, siz[v]) {
                f[u][i+j] = (f[u][i+j] + 1ll * g[i] * f[v][j] % mod * inv[j] % mod * inv[siz[v]-j-w] % mod) % mod;
            }
        } 
        siz[u] += siz[v];
    }
    f[u][0] = 1ll * f[u][0] * fac[siz[u]-1] % mod;
    re(i, siz[u]) f[u][i] = 1ll * f[u][i] * fac[i-1] % mod * fac[siz[u]-i-flg] % mod;
    
    if(u == rt) {
        re(i, siz[u]) f[u][i] = 0;
        return 1;
    }
    if(flg) {
        f[u][0] = 0;
    }
    return flg;
}

int main () {
    read(n);
    rep(i, 2, n) {
        read(fath[i]);
        G[fath[i]].pb(i);
    }
    re(i, n) read(b[i]);
    fac[0] = inv[0] = 1;
    re(i, n) fac[i] = 1ll * fac[i-1] * i % mod, inv[i] = ksm(fac[i], mod-2);
    for(rt=1; rt<=n; ++rt) {
        dfs(1);
        int ans = 0;
        rep(i, 0, n-1) {
            ans = (ans + 1ll * f[1][i] * b[i+1] % mod) % mod; 
        }
        out(ans);
    }
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 9680kb

input:

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

output:

791644175 293112286 383600722 383600722 556722198 47472573 200339152 378530675 47472573 378530675 

result:

wrong answer 1st numbers differ - expected: '132551152', found: '791644175'

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
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%