QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#732505#9566. Topologyquark404#WA 4ms7740kbC++203.2kb2024-11-10 14:55:082024-11-10 14:55:08

Judging History

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

  • [2024-11-10 14:55:08]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:7740kb
  • [2024-11-10 14:55:08]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e3 + 10;
vector<int> e[maxn];
const int mod = 998244353;
int ans[maxn];
int g[maxn];
int f[maxn][maxn];
int sz[maxn];
int n;
int fact[maxn], invfact[maxn];
void sz_dfs(int u, int fa)
{
    sz[u] = 1;
    for (auto x : e[u])
    {
        sz_dfs(x, u);
        sz[u] += sz[x];
    }
}
int qpow(int x, int y)
{
    int res = 1;
    while (y)
    {
        if (y & 1)
        {
            res = res * x % mod;
        }
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}
void init()
{
    fact[1] = invfact[1] = fact[0] = invfact[0] = 1;
    for (int i = 2; i < maxn; i++)
    {
        fact[i] = fact[i - 1] * i % mod;
    }
    invfact[maxn - 1] = qpow(fact[maxn - 1], mod - 2);
    for (int i = maxn - 2; i; i--)
    {
        invfact[i] = invfact[i + 1] * (i + 1) % mod;
    }
}
int C(int x, int y)
{
    if (x < y)
        return 0;
    else
    {
        return fact[x] * invfact[y] % mod * invfact[x - y] % mod;
    }
}
void g_dfs(int u, int fa)
{
    g[u] = 1;
    int tot = sz[u] - 1;
    for (auto x : e[u])
    {
        g_dfs(x, u);
        g[u] = g[u] * C(tot, sz[x]) % mod * g[x] % mod;
        tot -= sz[x];
    }
}
int find(int k, int n1) // k个位子,放n1个元素
{
    return C(k + n1 - 1, k - 1);
}
void dfs(int u, int fa)
{
    int tot = 1;
    // tot 代表将所有e[u].size()儿子中元素排序
    for (auto x : e[u])
    {
        assert(C(sz[u] - 1, sz[x]) != 0);
        assert(g[x] != 0);
        int g2 = g[u] * qpow(C(sz[u] - 1, sz[x]), mod - 2) % mod * qpow(g[x], mod - 2) % mod;
        // cout << x << ' ' << u << ' ' << g2 << endl;
        int len = n - sz[u] + 1;
        // cout << len << endl;
        for (int y_fa = 1; y_fa <= n; y_fa++)
        { // f[1][1]
            if (len < y_fa)
                break;
            //
            int left_len = len - y_fa + 1;
            // cout << left_len << endl;
            // f[u][y_fa]转移
            int val = f[u][y_fa] * find(left_len, sz[u] - 1 - sz[x]) * g2 % mod;
            // cout << val << ?endl;
            f[x][y_fa + 1] += val;
            // for (int y = y_fa + 1; y <= n; y++)
            // {
            //     f[x][y] += val;
            // }
            f[x][y_fa + 1] %= mod;
        }
        for (int y = 1; y <= n; y++)
        {
            f[x][y] += f[x][y - 1];
            f[x][y] %= mod;
        }
        dfs(x, u);
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    init();
    for (int i = 2; i <= n; i++)
    {
        int x;
        cin >> x;
        e[x].push_back(i);
    }
    sz_dfs(1, 0);
    g_dfs(1, 0);
    f[1][1] = 1;
    dfs(1, 0);
    // cout << f[2][2] << endl;
    // cout << g[1] << ' ';
    for (int i = 1; i <= n; i++)
    {
        int v = f[i][i];
        // son:
        // int len = n - sz[i] + 1;
        // n-sz[i]
        int totlen = n - sz[i] + 1 - i + 1;

        // cout << find(n - sz[i], sz[i] - 1) << endl;
        v = v * find(totlen, sz[i] - 1) % mod * g[i] % mod;
        cout << v << ' ';
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3688kb

input:

4
1 1 2

output:

3 2 1 2 

result:

ok 4 number(s): "3 2 1 2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

9
1 1 2 2 3 3 4 5

output:

672 420 180 160 152 108 120 170 210 

result:

ok 9 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

2
1

output:

1 1 

result:

ok 2 number(s): "1 1"

Test #4:

score: -100
Wrong Answer
time: 4ms
memory: 7740kb

input:

500
1 2 3 4 5 6 7 7 8 10 8 10 11 4 11 12 12 17 15 13 21 21 22 5 16 9 24 28 28 19 29 27 17 33 23 3 33 27 30 9 25 34 16 26 30 34 46 45 41 14 43 49 43 35 39 37 26 48 52 58 51 56 51 55 19 48 63 36 67 69 54 60 71 61 29 40 32 77 73 55 66 42 77 72 71 69 62 83 46 64 88 39 83 36 89 94 47 98 57 61 38 80 78 88...

output:

331058271 331058271 107893248 201481008 579367731 575070429 578212032 -644994296 689280130 78112040 81735938 302063994 432198372 -179227127 -544695592 -160268776 948217021 980258217 76088385 476130387 -906884017 -98589587 911777773 -507808877 574191638 -471421285 57235577 813753949 254503182 -438496...

result:

wrong answer 6th numbers differ - expected: '934007150', found: '575070429'