QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#72678#4811. Be Carefulyzc2005WA 2ms3656kbC++174.7kb2023-01-17 21:05:112023-01-17 21:05:14

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:05:14]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3656kb
  • [2023-01-17 21:05:11]
  • 提交

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_parity(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;
    vector<vector<int>> f(lim + 2, 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]);
        }
    }

    reverse(v2.begin(), v2.end());
    v3.erase(v3.begin(), v3.begin() + cnt_small);
    reverse(v3.begin(), v3.end());
    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(), --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: 100
Accepted
time: 1ms
memory: 3656kb

input:

5
1 2
1 3
2 4
2 5

output:

55
127
34
0
0
0

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 2ms
memory: 3532kb

input:

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

output:

69632
265534
133905
47790
12636
1944
0
0
0

result:

ok 9 numbers

Test #3:

score: 0
Accepted
time: 2ms
memory: 3516kb

input:

3
1 2
2 3

output:

1
3
0
0

result:

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

Test #4:

score: 0
Accepted
time: 2ms
memory: 3648kb

input:

2
1 2

output:

2
1
0

result:

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

Test #5:

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

input:

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

output:

1755647
612579511
359376750
200038110
104287680
49974120
21379680
7771680
2177280
362880
0

result:

ok 11 numbers

Test #6:

score: 0
Accepted
time: 1ms
memory: 3520kb

input:

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

output:

114358881
100000000
0
0
0
0
0
0
0
0
0

result:

ok 11 numbers

Test #7:

score: 0
Accepted
time: 1ms
memory: 3580kb

input:

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

output:

10
1
0
0
0
0
0
0
0
0
0

result:

ok 11 numbers

Test #8:

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

input:

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

output:

5869541
994668763
996111453
0
0
0
0
0
0
0
0

result:

wrong answer 1st numbers differ - expected: '27510', found: '5869541'