QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#72683#4811. Be Carefulyzc2005RE 0ms0kbC++174.8kb2023-01-17 21:41:402023-01-17 21:41:42

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-17 21:41:42]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-01-17 21:41:40]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int P = 998244353;
void add(int &x, int y) { (x += y) >= P && (x -= P); }
int Add(int x, int y) { return (x += y) >= P ? (x - P) : x; }
void sub(int &x, int y) { (x -= y) < 0 && (x += P); }
int Sub(int x, int y) { return (x -= y) < 0 ? (x + P) : x; }
void mul(int &x, int y) { x = 1ll * x * y % P; }
int Mul(int x, int y) { return 1ll * x * y % P; }

const int N = 205;
int n, dp[N][N], siz[N], pw[N][N], siz1[N];
vector<int> e[N];
 
void dfs(int u) {
    if (!e[u].size()) {
        siz1[u] = 1;
        return;
    }
    int cnt_leaf = 0;
    vector<int> sons;
    for (auto v : e[u]) {
        e[v].erase(find(e[v].begin(), e[v].end(), u));
        dfs(v), cnt_leaf += !e[v].size();
        siz1[u] += siz1[v];
        if (e[v].size()) sons.push_back(v);
    }
    sort(sons.begin(), sons.end(), [&](int u, int v) {
        return siz[u] < siz[v];
    });
    int mn = 1e9, B = -1;
    for (int b = 1; b <= 18; ++b) {
        int val = b;
        for (auto v : sons) val += (siz[v] >= b);
        if (val < mn) mn = val, B = b;
    }

    int lim = min((int) e[u].size(), (sons.empty() ? 0 : (siz[sons.back()] + 1)) + cnt_leaf);
    vector<vector<int>> v1, v2;
    vector<int> v3;
    for (auto v : sons) {
        if (siz[v] >= B) v2.push_back({dp[v], dp[v] + siz[v] + 1});
        vector<int> sum(1 << B, 0);
        for (int s = 1; s < 1 << B; ++s) {
            int i = __builtin_ctz(s);
            sum[s] = Add(sum[s ^ (1 << i)], dp[v][i]);
        }
        v1.push_back(sum);
        v3.push_back(pw[n + 1][siz1[v]]);
    }

    for (int p = 0; p < B; ++p) {
        for (int s = 0; s < 1 << p; ++s) {
            int cnt = __builtin_popcount(s) + n - p + 1;
            int coef = __builtin_parity(s) ? Sub(0, pw[cnt][cnt_leaf]) : pw[cnt][cnt_leaf];
            for (int i = 0; i < (int) sons.size(); ++i) mul(coef, Add(v1[i][s], v3[i]));
            add(dp[u][p], coef);
        }
        for (int i = 0; i < (int) sons.size(); ++i) sub(v3[i], dp[sons[i]][p]);
    }

    int cnt_large = v2.size(), cnt_small = v1.size() - cnt_large;
    reverse(v1.begin() + cnt_small, v1.end());
    reverse(v2.begin(), v2.end());
    v3.erase(v3.begin(), v3.begin() + cnt_small);
    reverse(v3.begin(), v3.end());
    vector<vector<int>> f(lim + 1, vector<int>(1 << cnt_large, 0));
    vector<int> vals(1 << cnt_large);
    for (int s = 0; s < 1 << B; ++s) {
        int coef = 1;
        for (int i = 0; i < cnt_small; ++i) mul(coef, v1[i][s]);
        for (int msk = 0; msk < 1 << cnt_large; ++msk) {
            if (msk == 0) {
                vals[msk] = coef;
            } else {
                int i = __builtin_ctz(msk);
                vals[msk] = Mul(vals[msk ^ (1 << i)], v1[cnt_small + i][s]);
            }
            int c = __builtin_popcount(s);
            add(f[c][msk ^ ((1 << cnt_large) - 1)], vals[msk]);
        }
    }

    for (int p = B; p <= lim; ++p) {
        vector<int> prd(1 << cnt_large, 1);
        for (int s = 1; s < 1 << cnt_large; ++s) {
            int i = __builtin_ctz(s);
            prd[s] = Mul(prd[s ^ (1 << i)], v3[i]);
        }
        for (int c = 0; c <= p; ++c) {
            for (int s = 0; s < 1 << cnt_large; ++s) {
                int val = Mul(f[c][s], prd[s]);
                if (c & 1) val = Sub(0, val);
                add(dp[u][p], Mul(val, pw[c + n - p + 1][cnt_leaf]));
            }
        }
        while (!v2.empty() && (int) v2.back().size() == p) {
            v2.pop_back(), v3.pop_back(), --cnt_large;
            for (auto &g : f) g.resize(1 << cnt_large);
        }
        for (int i = 0; i < cnt_large; ++i) sub(v3[i], v2[i][p]);
        for (int c = p; ~c; --c) {
            auto g = f[c];
            for (int i = 0; i < cnt_large; ++i) {
                int val = v2[i][p];
                for (int k = 0; k < 1 << cnt_large; k += 2 << i) {
                    for (int j = 0; j < 1 << i; ++j) {
                        add(g[k | j], Mul(g[k | j | 1 << i], val));
                    }
                }
            }
            for (int s = 0; s < 1 << cnt_large; ++s) add(f[c + 1][s], g[s]);
        }
    }

    for (int i = 1; i <= n; i += 2) dp[u][i] = Sub(0, dp[u][i]);
    for (int i = 0; i < n; ++i) sub(dp[u][i], dp[u][i + 1]);
    siz[u] = n;
    while (!dp[u][siz[u]]) --siz[u];
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);

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

    dfs(1);
    for (int i = 0; i <= n; ++i) cout << dp[1][i] << "\n";

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

5
1 2
1 3
2 4
2 5

output:


result: