QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#642076#4811. Be CarefulhhoppitreeTL 286ms22092kbC++173.8kb2024-10-15 09:45:122024-10-15 09:45:14

Judging History

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

  • [2024-10-15 09:45:14]
  • 评测
  • 测评结果:TL
  • 用时:286ms
  • 内存:22092kb
  • [2024-10-15 09:45:12]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 205, P = 998244353;

vector<int> G[N];
int n, dp[N][N], sdp[N][N], f[2][1 << 20], g[2][1 << 20][N], 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] = (sdp[v][i + 1] + dp[v][i]) % P;
            }
            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)] = (f[0][j | (1 << k)] + 1ll * f[1][j] * dp[o[i].second][k]) % P;
            }
        }
    }
    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[0][j][k] = 0;
        }
        g[0][(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[0][k][l]) ok = 1;
                    g[1][k][l] = g[0][k][l], g[0][k][l] = 0;
                }
            }
            if (!ok) break;
            for (int k = 0; k < (1 << z); ++k) {
                for (int l = 0; l <= cnt; ++l) if (g[1][k][l]) {
                    for (int K = k, tk = -1; tk; tk = K, K = (K - 1) & k) {
                        for (int L = 0; L <= l; ++L) {
                            if (!K && !L && !((i >> j) & 1)) continue;
                            int mul = 1ll * g[1][k][l] * C[l][L] % P;
                            for (int p = 0; p < z; ++p) {
                                if ((K >> p) & 1) {
                                    mul = 1ll * mul * dp[o[ps + 1 + p].second][j] % P;
                                }
                            }
                            g[0][k ^ K][l - L] = (g[0][k ^ K][l - L] + mul) % P;
                        }
                    }
                    if ((i >> j) & 1) continue;
                    int mul = g[1][k][l];
                    for (int t = 1; t <= l; ++t) mul = 1ll * mul * (n - j) % P;
                    for (int p = 0; p < z; ++p) {
                        if ((k >> p) & 1) {
                            mul = 1ll * mul * sdp[o[ps + 1 + p].second][j + 1] % P;
                        }
                    }
                    dp[x][j] = (dp[x][j] + mul) % P;
                }
            }
        }
    }
}

signed main() {
    // freopen("mex.in", "r", stdin);
    // freopen("mex.out", "w", stdout);
    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]);
    return 0;
}

詳細信息

Test #1:

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

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

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

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

input:

2
1 2

output:

2
1
0

result:

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

Test #5:

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

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

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

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: 0
Accepted
time: 1ms
memory: 8188kb

input:

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

output:

27510
31142
102399
0
0
0
0
0
0
0
0

result:

ok 11 numbers

Test #9:

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

input:

14
10 3
6 2
2 8
3 13
1 3
1 2
3 14
4 2
9 3
12 3
2 5
7 2
11 3

output:

930962871
780146137
253920328
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 15 numbers

Test #10:

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

input:

20
7 6
2 6
5 1
17 12
9 13
12 18
3 2
9 1
2 1
12 6
10 9
14 2
4 1
6 8
11 2
16 9
13 19
8 15
20 5

output:

572808214
694156482
763085092
958730326
465749894
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 21 numbers

Test #11:

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

input:

21
6 12
11 13
1 7
8 14
1 18
5 4
1 2
16 11
21 1
9 10
15 17
1 9
1 8
1 20
1 3
1 4
19 16
11 1
15 10
3 6

output:

778184256
242901486
277265229
855621813
564317020
918444623
408876720
314039448
593931360
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 22 numbers

Test #12:

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

input:

22
20 21
9 12
6 10
19 10
16 10
10 11
8 7
13 12
21 22
19 20
14 13
7 6
8 9
15 14
2 5
18 6
5 6
3 2
16 17
2 1
3 4

output:

142157709
5878180
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 23 numbers

Test #13:

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

input:

23
6 10
4 2
6 9
15 20
10 15
3 6
17 23
1 3
16 22
19 14
17 12
7 11
18 13
11 16
5 3
8 5
10 14
8 12
9 13
4 7
1 2
15 21

output:

7619809
175546557
7936610
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 24 numbers

Test #14:

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

input:

24
7 10
2 5
2 1
17 20
1 4
16 13
7 4
19 16
23 20
11 8
10 13
1 3
22 19
5 8
3 6
17 14
21 18
24 21
18 15
9 6
9 12
14 11
15 12

output:

24
576
15025
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 25 numbers

Test #15:

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

input:

24
22 16
17 11
15 9
13 7
8 2
1 3
5 1
6 12
9 3
14 8
21 15
17 23
19 13
7 1
24 18
2 1
5 11
1 4
4 10
18 12
20 14
10 16
1 6

output:

24
7962624
236177977
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 25 numbers

Test #16:

score: 0
Accepted
time: 10ms
memory: 8384kb

input:

200
1 199
95 1
1 75
177 1
66 1
157 1
85 1
1 193
1 26
8 1
38 1
151 1
1 56
63 1
1 138
1 59
190 1
1 36
1 120
156 1
115 1
1 118
171 1
6 1
113 1
20 1
83 1
1 176
33 1
153 1
1 169
22 1
1 159
1 27
87 1
1 129
1 44
174 1
1 93
77 1
1 122
1 125
1 23
1 81
112 1
173 1
1 51
32 1
96 1
184 1
116 1
67 1
1 94
1 104
19...

output:

211917199
369375874
201944418
582671162
183066248
639389350
952947539
137147613
216366713
398936459
73236543
354059031
727857197
121548413
610762100
573534011
706945631
286154195
226699593
267771858
823273748
233587424
176942776
226493975
707601105
339075191
694353149
944734662
932707579
934386415
4...

result:

ok 201 numbers

Test #17:

score: 0
Accepted
time: 10ms
memory: 8472kb

input:

200
2 199
95 2
2 75
177 2
66 2
157 2
85 2
2 193
2 26
8 2
38 2
151 2
2 56
63 2
2 138
2 59
190 2
2 36
2 120
156 2
115 2
2 118
171 2
6 2
113 2
20 2
83 2
2 176
33 2
153 2
2 169
22 2
2 159
2 27
87 2
2 129
2 44
174 2
2 93
77 2
2 122
2 125
2 23
2 81
112 2
173 2
2 51
32 2
96 2
184 2
116 2
67 2
2 94
2 104
19...

output:

356210711
85910356
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 201 numbers

Test #18:

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

input:

200
198 199
95 94
74 75
177 176
66 65
157 156
85 84
192 193
25 26
8 7
38 37
151 150
55 56
63 62
137 138
58 59
190 189
35 36
119 120
156 155
115 114
117 118
171 170
6 5
113 112
20 19
83 82
175 176
33 32
153 152
168 169
22 21
158 159
26 27
87 86
128 129
43 44
174 173
92 93
77 76
121 122
124 125
22 23
...

output:

200
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #19:

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

input:

199
176 177
115 116
47 48
29 30
120 119
7 8
93 94
158 159
118 117
28 29
185 186
133 132
24 25
76 77
55 54
68 69
96 95
65 66
172 171
114 113
127 128
91 92
106 107
70 71
135 136
83 82
187 188
146 147
23 22
36 37
195 196
166 165
81 80
109 108
8 9
21 20
41 42
125 124
46 47
87 86
133 134
38 37
174 173
12...

output:

1
199
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 200 numbers

Test #20:

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

input:

200
28 56
82 165
53 107
94 188
67 134
51 102
69 139
18 37
10 20
33 66
179 89
156 78
53 106
93 186
113 56
9 19
8 16
65 130
33 16
41 82
37 74
197 98
26 53
18 36
195 97
30 60
132 66
81 162
61 30
40 81
26 52
168 84
79 39
128 64
27 54
68 136
91 45
40 20
122 61
108 54
3 6
118 59
91 182
177 88
15 31
133 66...

output:

115157040
769068498
218666068
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #21:

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

input:

200
51 153
118 39
23 68
26 9
163 54
7 2
21 62
174 58
125 42
50 150
15 46
32 95
186 62
53 158
7 22
29 88
165 55
47 140
9 3
18 6
20 59
131 44
90 30
149 50
35 12
11 32
15 5
4 13
110 37
160 53
3 10
51 152
154 51
37 12
94 31
119 40
49 146
196 65
16 48
46 138
4 12
116 39
74 25
27 81
105 35
61 182
18 55
19...

output:

96831322
243739289
839032182
347339046
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 201 numbers

Test #22:

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

input:

200
4 1
40 159
6 22
16 65
7 29
7 2
10 39
103 26
24 97
180 45
24 6
47 186
50 200
140 35
15 61
10 38
127 32
93 23
18 73
185 46
23 91
29 115
126 32
35 9
120 30
22 86
20 79
7 27
35 139
148 37
26 105
18 70
198 50
190 48
136 34
147 37
25 98
39 155
40 158
199 50
67 17
75 19
8 2
109 27
160 40
176 44
23 90
1...

output:

868579713
768926703
473674519
835466001
35818891
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 201 numbers

Test #23:

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

input:

200
124 21
53 9
5 28
33 199
145 24
20 119
24 140
31 5
86 15
30 176
12 69
172 29
116 20
14 3
11 66
3 15
75 13
13 76
144 24
79 13
72 12
80 14
1 7
70 12
23 135
178 30
33 197
30 179
9 55
27 159
18 3
25 151
11 62
18 107
82 14
30 180
23 138
31 182
16 94
97 16
93 16
173 29
32 190
10 2
8 2
18 104
6 35
111 1...

output:

298503373
243520600
324348437
233414660
209600209
600025942
504289019
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #24:

score: 0
Accepted
time: 12ms
memory: 9208kb

input:

200
6 61
5 47
14 141
16 161
144 15
48 5
115 12
147 15
175 18
19 186
86 9
75 8
109 11
158 16
169 17
62 7
135 14
97 10
1 6
3 23
9 87
42 5
73 8
20 200
152 16
14 132
90 9
21 2
4 34
4 37
181 18
71 7
1 9
84 9
180 18
56 6
127 13
6 52
12 121
137 14
7 64
11 105
156 16
15 146
6 59
1 4
83 9
8 74
6 60
69 7
10 1...

output:

107615921
75193607
506753286
400364397
127708406
597309377
407829846
269700097
404852842
311884298
159659723
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 201 numbers

Test #25:

score: 0
Accepted
time: 85ms
memory: 14332kb

input:

200
83 7
8 92
107 9
31 3
19 2
6 72
140 12
186 16
22 2
131 11
6 66
14 169
21 2
120 10
16 193
39 4
85 7
15 177
155 13
183 16
176 15
4 47
4 38
110 10
12 143
3 37
11 122
171 15
69 6
195 17
9 102
144 12
158 14
1 8
166 14
117 10
13 154
179 15
17 194
88 8
6 64
2 23
15 181
14 160
17 197
173 15
81 7
147 13
8...

output:

820487232
168056104
389303904
786803166
747859949
163201436
184471655
286943236
734039879
217802148
477672105
313993286
576453384
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #26:

score: 0
Accepted
time: 286ms
memory: 22092kb

input:

200
101 8
56 5
140 11
15 193
10 129
5 54
6 68
200 16
13 161
13 169
170 13
162 13
102 8
134 11
1 6
130 10
3 33
15 188
2 17
13 163
71 6
4 51
22 2
149 12
8 96
3 30
7 82
143 11
34 3
119 10
6 76
67 6
46 4
9 108
78 6
113 9
4 50
11 132
3 29
172 14
13 167
16 199
5 62
4 1
144 11
10 121
26 2
15 194
11 1
39 3
...

output:

941560284
156408143
117860855
71504118
286002901
82236540
656386501
984288699
392292354
375678581
525101177
448561345
88856629
222487029
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 201 numbers

Test #27:

score: -100
Time Limit Exceeded

input:

200
50 4
2 21
175 13
181 13
13 178
9 121
2 17
2 22
169 12
1 5
5 62
11 1
10 138
141 10
185 14
85 6
70 5
3 40
109 8
9 124
67 5
173 13
180 13
42 3
15 199
81 6
7 87
3 39
2 24
79 6
9 117
143 11
187 14
8 111
14 191
12 162
72 6
6 1
184 14
12 166
149 11
1 2
125 9
3 31
192 14
2 26
37 3
4 54
6 73
10 128
76 6
...

output:

306791307
41136979
825727064
348896251
156923421
279326908
271414153
908884019
949859290
556906447
15321817
192929720
228240965
575859246
416336706
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result: