QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#634057#5139. DFS Order 2333zhanWA 1ms3872kbC++202.9kb2024-10-12 16:38:392024-10-12 16:38:44

Judging History

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

  • [2024-10-12 16:38:44]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3872kb
  • [2024-10-12 16:38:39]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long

using namespace std;

constexpr int mod = 998244353;

void solve () {
    int n;
    cin >> n;

    vector <int> fac (n + 1);
    fac[0] = 1;
    for (int i = 1; i <= n; i ++) {
        fac[i] = fac[i - 1] * i % mod;
    }

    vector <vector <int>> e (n);
    for (int i = 1; i < n; i ++) {
        int x, y;
        cin >> x >> y;
        x --; y --;
        e[x].push_back (y);
        e[y].push_back (x);
    }

    vector <int> sz (n, 1);
    vector <int> dp (n, 1);

    auto dfs1 = [&] (auto &&self, int x, int fa) -> void {
        int son = 0;
        for (auto y : e[x]) {
            if (y == fa) {
                continue;
            }
            son ++;
            self (self, y, x);
            sz[x] += sz[y];
            dp[x] *= dp[y];
            dp[x] %= mod;
        }
        dp[x] = dp[x] * fac[son] % mod;
    };
    dfs1 (dfs1, 0, -1);

    vector ans (n, vector <int> (n + 1));
    ans[0][1] = dp[0];

    auto dfs2 = [&] (auto &&self, int x, int fa) -> void {
        vector <int> g (n + 1);
        g[0] = 1;
        for (auto y : e[x]) {
            if (y == fa) {
                continue;
            }
            auto ng = g;
            for (int i = sz[y]; i <= n; i ++) {
                ng[i] += g[i - sz[y]] * dp[y];
                ng[i] %= mod;
            }
            g = move (ng);
        }
        // if (x + 1 == 3) {
        //     for (int i = 1; i <= n; i ++) {
        //         cerr << g[i] << " \n"[i == n];
        //     }
        // }
        for (auto y : e[x]) {
            if (y == fa) {
                continue;
            }
            auto f = g;
            for (int i = sz[y]; i <= n; i ++) {
                f[i] -= dp[y] * f[i - sz[y]];
                f[i] = (f[i] % mod + mod) % mod;
            }
            // if (y + 1 == 2) {
            //     for (int i = 0; i <= n; i ++) {
            //         cerr << f[i] << " \n"[i == n];
            //     }
            // }
            for (int ax = 1; ax < n; ax ++) {
                if (ans[x][ax]) {
                    for (int ay = ax + 1; ay <= n; ay ++) {
                        ans[y][ay] += f[ay - ax - 1] * f[sz[x] - 1 - (ay - ax - 1) - sz[y]] % mod * dp[y];
                        ans[y][ay] %= mod;
                    }
                }
            }
        }
        for (int y : e[x]) {
            if (y == fa) {
                continue;
            }
            self (self, y, x);
        }
    };
    dfs2 (dfs2, 0, -1);

    for (int i = 0; i < n; i ++) {
        for (int j = 1; j <= n; j ++) {
            cout << ans[i][j] << " \n"[j == n];
        }
    }
}

signed main () {
    ios::sync_with_stdio (false);
    cin.tie (nullptr);

    int T = 1;
    // cin >> T;

    while (T --) {
        solve ();
    }

    return 0;
}

详细

Test #1:

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

input:

5
1 2
1 3
3 4
3 5

output:

4 0 0 0 0
0 2 0 0 2
0 2 2 0 0
0 0 1 2 1
0 0 1 2 1

result:

ok 25 numbers

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3872kb

input:

10
9 2
9 6
10 5
1 5
1 6
9 3
5 8
4 3
7 9

output:

24 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 2 1 1 1
0 0 0 1 4 1 1 4 1 0
0 0 0 0 1 1 1 1 1 1
0 12 0 0 0 0 0 12 0 0
0 12 0 0 12 0 0 0 0 0
0 0 0 1 1 1 2 1 1 1
0 0 1 1 0 0 0 0 1 1
0 0 6 0 0 6 0 0 0 0
0 0 1 1 0 0 0 0 1 1

result:

wrong answer 14th numbers differ - expected: '4', found: '1'