QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#239026#5139. DFS Order 2tselmegkh#WA 1ms3476kbC++174.0kb2023-11-04 18:09:112023-11-04 18:09:12

Judging History

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

  • [2023-11-04 18:09:12]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3476kb
  • [2023-11-04 18:09:11]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T>
T power(T a, long long b) {
    T s = 1;
    for (; b; a *= a, b >>= 1) if (b & 1) s *= a;
    return s;
}
template <int mod>
struct modular {
    using mint = modular;
    int v;
    modular() : v(0) {}
    modular(long long x) {if ((v = x % mod) < 0) v += mod;}
    mint operator-() const {return -v;}
    mint inv() const {return power(*this, mod - 2);}
    mint &operator+=(const mint &a) {if ((v += a.v) >= mod) v -= mod; return *this;}
    mint &operator-=(const mint &a) {if ((v -= a.v) < 0) v += mod; return *this;}
    mint &operator*=(const mint &a) {v = (int)((long long)v * a.v % mod); return *this;}
    mint &operator/=(const mint &a) {return *this *= a.inv();}
    friend bool operator==(const mint &a, const mint &b){return a.v == b.v;}
    friend bool operator!=(const mint &a, const mint &b){return a.v != b.v;}
    friend mint operator+(const mint &a, const mint &b) {return mint(a) += b;}
    friend mint operator-(const mint &a, const mint &b) {return mint(a) -= b;}
    friend mint operator*(const mint &a, const mint &b) {return mint(a) *= b;}
    friend mint operator/(const mint &a, const mint &b) {return mint(a) /= b;}
    friend istream &operator>>(istream &is, mint &a) {return is >> a.v;}
    friend ostream &operator<<(ostream &os, const mint &a) {return os << a.v;}
};
const int mod = 998244353;
using mint = modular<mod>;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<mint> fac(n + 1);
    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i;
    }
    vector C(n + 1, vector<mint>(n + 1));
    for (int i = 0; i <= n; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
        }
    }
    vector<vector<int>> adj(n);
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    vector<mint> s(n, 1), q(n, 1);
    vector<int> sz(n), ch(n);
    auto calc = [&](auto calc, int x, int p) -> void {
        sz[x] = 1;
        for (int y : adj[x]) {
            if (y == p) continue;
            ch[x]++;
            calc(calc, y, x);
            s[x] *= s[y];
            sz[x] += sz[y];
        }
        for (int y : adj[x]) {
            for (int z : adj[x]) {
                if (z == y || z == p) continue;
                q[y] *= s[z];
            }
        }
        s[x] *= fac[ch[x]];
    };
    calc(calc, 0, -1);
    vector dp(n, vector<mint>(n));
    mint t = 1;
    auto dfs = [&](auto dfs, int x, int p) -> void {
        for (int y : adj[x]) {
            if (y == p) continue;
            int m = adj[x].size();
            vector a(ch[x] + 1, vector<mint>(sz[x]));
            a[0][0] = 1;
            for (int z : adj[x]) {
                if (z == y || z == p) continue;
                for (int i = 0; i < ch[x]; i++) {
                    for (int j = sz[z]; j < sz[x]; j++) {
                        a[i + 1][j] += a[i][j - sz[z]];
                    }
                }
            }
            vector<mint> b(sz[x]);
            for (int i = 0; i <= ch[x]; i++) {
                for (int j = 0; j < sz[x]; j++) {
                    b[j] += a[i][j] * C[ch[x] - 1][i];
                }
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (i - j - 1 >= sz[x]) continue;
                    dp[y][i] += dp[x][j] * b[i - j - 1];
                }
            }
            t *= q[y];
            dfs(dfs, y, x);
            t /= q[y];
        }
        for (int i = 0; i < n; i++) {
            dp[x][i] *= t * s[x];
        }
    };
    dp[0][0] = 1;
    dfs(dfs, 0, -1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << dp[i][j] << " \n"[j == n - 1];
        }
    }
}

详细

Test #1:

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

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: 1ms
memory: 3476kb

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 2 4 6 4 6 6 2
0 0 0 2 8 6 2 8 6 0
0 0 0 0 2 8 6 2 8 6
0 12 0 0 0 0 0 12 0 0
0 12 0 0 12 0 0 0 0 0
0 0 0 2 4 6 4 6 6 2
0 0 6 6 0 0 0 0 6 6
0 0 12 0 0 12 0 0 0 0
0 0 6 6 0 0 0 0 6 6

result:

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