QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#642136#4811. Be CarefulhhoppitreeWA 1ms8220kbC++174.1kb2024-10-15 10:45:372024-10-15 10:45:38

Judging History

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

  • [2024-10-15 10:45:38]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8220kb
  • [2024-10-15 10:45:37]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 205, P = 998244353;

struct MOD {
    int operator ()(long long x) {
        return x - (((__int128)x * 18479187002) >> 64) * P;
    }
} mod;

vector<int> G[N];
int n, dp[N][N], sdp[N][N], f[2][1 << 18], g[1 << 18][N], h[1 << 18], S[1 << 18], C[N][N];

void dfs(int x, int fa = -1) {
    int deg = 0, cnt = 0;
    for (auto v : G[x]) {
        if (v != fa) {
            dfs(v, x);
            for (int i = n; i >= 0; --i) {
                sdp[v][i] = mod(sdp[v][i + 1] + dp[v][i]);
            }
            cnt += (G[v].size() == 1), ++deg;
        }
    }
    if (!deg) {
        fill(dp[x], dp[x] + n + 1, 1);
        return;
    }
    vector< pair<int, int> > o;
    for (auto v : G[x]) {
        if (v != fa && G[v].size() != 1) {
            int L = n;
            while (!dp[v][L]) --L;
            o.push_back({L, v});
        }
    }
    sort(o.begin(), o.end());
    int mn = o.size() + 1, ps = -1;
    for (int i = 0; i < (int)o.size(); ++i) {
        if (o[i].first + ((int)o.size() - i) < mn) {
            mn = o[i].first + ((int)o.size() - i), ps = i;
        }
    }
    int tz = (!~ps ? 0 : o[ps].first + 1);
    for (int i = 0; i < 1 << tz; ++i) f[0][i] = !i;
    for (int i = 0; i <= ps; ++i) {
        for (int j = 0; j < 1 << tz; ++j) f[1][j] = f[0][j], f[0][j] = 0;
        for (int j = (1 << (o[i].first + 1)) - 1; ~j; --j) {
            for (int k = 0; k <= o[i].first; ++k) {
                f[0][j | (1 << k)] = mod(f[0][j | (1 << k)] + 1ll * f[1][j] * dp[o[i].second][k]);
            }
        }
    }
    for (int i = 0; i < 1 << tz; ++i) if (f[0][i]) {
        int z = o.size() - 1 - ps;
        for (int j = 0; j < (1 << z); ++j) {
            for (int k = 0; k <= cnt; ++k) g[j][k] = 0;
        }
        g[(1 << z) - 1][cnt] = f[0][i];
        for (int j = 0; ; ++j) {
            int ok = 0;
            for (int k = 0; k < (1 << z); ++k) {
                for (int l = 0; l <= cnt; ++l) {
                    if (g[k][l] %= P) ok = 1;
                }
            }
            if (!ok) break;
            int now = 1;
            for (int l = 0; l <= cnt; ++l) {
                if (l) now = mod(1ll * now * (n - j));
                vector< pair<int*, int> > del;
                for (int k = 0; k < (1 << z); ++k) {
                    h[k] = g[k][l];
                    del.push_back({&g[k][l], g[k][l]});
                    if (g[k][l] && (j >= 30 || !((i >> j) & 1))) {
                        del.push_back({&g[k][l], g[k][l]});
                        int mul = mod(1ll * g[k][l] * now);
                        if (!k) S[k] = 1;
                        else {
                            int pos = __builtin_ctz(k);
                            S[k] = mod(1ll * S[k ^ (1 << pos)] * sdp[o[ps + 1 + pos].second][j + 1]);
                        }
                        dp[x][j] = mod(dp[x][j] + 1ll * mul * S[k]);
                    }
                }
                for (int len = 2; len <= (1 << z); len <<= 1) {
                    int pos = o[ps + __builtin_ctz(len)].second;
                    for (int k = 0; k < (1 << z); k += len) {
                        for (int p = k; p < k + (len >> 1); ++p) {
                            h[p] = mod(h[p] + 1ll * h[p + (len >> 1)] * dp[pos][j]);
                        }
                    }
                }
                for (int k = 0; k < (1 << z); ++k) {
                    for (int L = 0; L <= l; ++L) {
                        g[k][L] = mod(g[k][L] + 1ll * h[k] * C[l][L]);
                    }
                }
                for (auto [x, y] : del) *x = mod(*x - y);
            }
        }
    }
}

signed main() {
    scanf("%d", &n);
    for (int i = C[0][0] = 1; i <= n; ++i) {
        for (int j = C[i][0] = 1; j <= i; ++j) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
        }
    }
    for (int i = 1, x, y; i < n; ++i) {
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1);
    for (int i = 0; i <= n; ++i) printf("%d\n", (dp[1][i] % P + P) % P);
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 8204kb

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: 0ms
memory: 8200kb

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

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

input:

2
1 2

output:

2
1
0

result:

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

Test #5:

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

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: 8220kb

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: 7936kb

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

input:

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

output:

2620
29000
102000
0
0
0
0
0
0
0
0

result:

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