QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#224916#7607. The Doubling Game 2ucup-team004#TL 859ms158848kbC++203.4kb2023-10-23 17:42:582023-10-23 17:42:59

Judging History

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

  • [2023-10-23 17:42:59]
  • 评测
  • 测评结果:TL
  • 用时:859ms
  • 内存:158848kb
  • [2023-10-23 17:42:58]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

constexpr int P = 1000000007;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::vector<std::vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        int a, b;
        std::cin >> a >> b;
        a--, b--;
        // a = i, b = a & (a - 1);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    std::vector<int> dp(n), mx(n);
    std::vector<std::array<int, 20>> f(n), g(n);
    auto dfs = [&](auto self, int x, int p) -> void {
        std::vector<int> a;
        for (auto y : adj[x]) {
            if (y == p) {
                continue;
            }
            self(self, y, x);
            a.push_back(mx[y]);
        }
        std::sort(a.begin(), a.end(), std::greater());
        int M = a.size();
        for (int i = 0; i < a.size(); i++) {
            M = std::min(M, a[i] + i + 1);
        }
        mx[x] = M;
        for (int v = 0; v <= M + 1; v++) {
            int L = std::min(v, M) + 1;
            std::vector<u64> h(1 << L), h1(1 << L);
            h[0] = 1;
            for (auto y : adj[x]) {
                if (y == p) {
                    continue;
                }
                for (int s = 0; s < (1 << L); s++) {
                    h1[s] = 1ULL * h[s] * dp[y];
                }
                for (int s = 0; s < (1 << L); s++) {
                    if (v <= M && (~s >> v & 1) && v <= mx[y]) {
                        int t = s | (1 << v);
                        h1[t] += 1ULL * h[s] * g[y][v];
                    }
                }
                for (int i = 0; i < v && i <= mx[y]; i++) {
                    for (int hi = 0; hi < (1 << L); hi += (2 << i)) {
                        for (int lo = 0; lo < (1 << i); lo++) {
                            int s = hi + lo;
                            int t = s | 1 << i;
                            h1[t] += 1ULL * h[s] * f[y][i];
                        }
                    }
                }
                // for (int s = (1 << L) - 1; s >= 0; s--) {
                //     int val = h[s];
                //     h[s] = 1ULL * val * dp[y];
                //     for (int i = 0; i < v && i <= mx[y]; i++) {
                //         if (~s >> i & 1) {
                //             int t = s | 1 << i;
                //             h[t] += 1ULL * val * f[y][i];
                //         }
                //     }
                //     if (v <= M && (~s >> v & 1) && v <= mx[y]) {
                //         int t = s | (1 << v);
                //         h[t] += 1ULL * val * g[y][v];
                //     }
                // }
                for (int s = (1 << L) - 1; s >= 0; s--) {
                    h[s] = h1[s] % P;
                }
            }
            if (v <= M) {
                f[x][v] = h[(1 << v) - 1];
                dp[x] = (dp[x] + f[x][v]) % P;
                dp[x] = (dp[x] + h[(2 << v) - 1]) % P;
            }
            for (int i = 0; i < v; i++) {
                g[x][i] = (g[x][i] + h[(1 << v) - 1 - (1 << i)]) % P;
                if (v <= M) {
                    g[x][i] = (g[x][i] + h[(2 << v) - 1 - (1 << i)]) % P;
                }
            }
        }
    };
    dfs(dfs, 0, -1);

    std::cout << dp[0] << "\n";

    return 0;
}

详细

Test #1:

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

input:

5
1 2
1 3
1 4
4 5

output:

21

result:

ok single line: '21'

Test #2:

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

input:

1

output:

1

result:

ok single line: '1'

Test #3:

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

input:

128
11 32
116 81
65 4
117 47
5 81
104 30
61 8
82 59
95 20
92 29
29 127
97 39
123 33
59 128
115 33
83 67
74 16
77 33
64 73
124 123
8 127
61 51
101 122
35 90
119 116
112 27
81 93
109 123
54 1
119 100
116 16
65 47
67 27
22 105
76 87
36 39
27 96
72 31
91 123
21 105
118 12
110 48
121 72
14 115
24 16
106 ...

output:

508800953

result:

ok single line: '508800953'

Test #4:

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

input:

256
53 177
57 242
74 90
107 104
209 169
132 70
152 142
71 168
143 99
91 130
202 140
49 165
209 193
209 137
159 188
247 48
49 21
20 208
155 185
120 231
83 87
37 84
143 18
106 8
114 79
191 158
208 256
133 252
215 92
199 108
166 168
39 217
85 69
204 139
100 75
111 6
230 198
79 130
26 155
155 38
55 81
1...

output:

999869740

result:

ok single line: '999869740'

Test #5:

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

input:

512
507 193
168 152
48 369
273 170
101 349
160 261
438 197
446 224
125 264
210 131
272 218
361 85
226 119
57 33
229 89
37 317
130 417
30 470
435 300
499 417
132 260
196 430
119 117
157 260
207 151
368 277
188 371
214 330
484 228
96 94
97 442
251 461
443 248
163 207
306 147
346 90
457 112
436 222
364...

output:

37387055

result:

ok single line: '37387055'

Test #6:

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

input:

1024
340 598
1 851
245 819
414 736
996 316
300 284
924 407
532 557
362 178
1006 469
397 373
742 77
112 37
406 892
703 666
496 825
1002 100
875 856
263 975
227 6
288 389
661 437
160 626
833 770
912 837
405 628
466 686
45 629
59 13
163 991
1017 422
208 247
344 376
709 956
570 272
996 954
518 454
267 3...

output:

689180079

result:

ok single line: '689180079'

Test #7:

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

input:

2048
2046 1942
589 1449
1593 1983
936 414
387 184
1962 1237
1986 635
573 1619
1598 1109
458 836
1123 1563
1502 519
1467 347
1815 864
980 405
709 433
1682 211
1967 1915
1089 1902
564 211
128 1004
1568 315
293 494
1552 1772
1641 1157
431 1899
1334 1623
161 1870
885 1330
1863 502
1761 1643
692 1759
118...

output:

275839338

result:

ok single line: '275839338'

Test #8:

score: 0
Accepted
time: 3ms
memory: 4276kb

input:

4096
2546 3568
3084 3426
1262 2128
1773 1455
425 3750
3444 3265
3099 464
3479 3651
639 1727
2486 2768
1165 1905
1847 2626
1335 3938
2550 1594
1520 1758
3771 2227
3486 60
381 383
1268 2829
1884 3468
3195 2892
983 31
584 2599
2811 1876
1875 3310
3184 2941
2893 202
1305 1926
1019 1639
3529 1998
2129 12...

output:

99235843

result:

ok single line: '99235843'

Test #9:

score: 0
Accepted
time: 5ms
memory: 5076kb

input:

8192
5663 2164
3712 1600
336 2388
1971 4169
1579 7319
496 8080
5305 982
5508 5777
5324 6680
4636 6745
7295 6086
6948 388
5239 811
1875 7271
5755 2864
2933 795
6448 6716
3016 302
2474 2937
6355 5936
4973 4064
2920 2318
6254 4090
665 2500
961 8180
5416 6371
4958 5430
7905 5013
4373 3068
6557 3867
3056...

output:

79832799

result:

ok single line: '79832799'

Test #10:

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

input:

16384
4535 8823
5344 1240
5793 15361
8423 14130
14595 11420
12195 1332
9712 4829
9533 14608
1328 14962
13846 1173
12823 5702
3518 9298
3235 13113
14312 3915
3439 9003
4667 5401
3819 2395
13827 981
3557 11804
7369 11344
15524 1435
4706 15539
12838 2109
4986 5367
2766 4313
6802 12338
12059 3998
6327 5...

output:

732760598

result:

ok single line: '732760598'

Test #11:

score: 0
Accepted
time: 19ms
memory: 10548kb

input:

32768
18706 23242
17650 5918
17278 24553
13070 18006
22702 10359
7113 13886
25578 16957
28955 27352
7353 6627
24042 21572
4744 30083
29267 16077
19328 1154
32271 23711
22390 3651
19272 7150
19081 13949
22123 4853
17958 18148
27675 28239
29486 26616
14292 23782
12790 18303
25184 9656
2671 13229
21875...

output:

383548244

result:

ok single line: '383548244'

Test #12:

score: 0
Accepted
time: 29ms
memory: 17720kb

input:

65536
58488 63309
5892 23044
42057 26219
45788 13164
16585 3001
4262 20408
60289 43446
44684 60172
60763 38228
56279 19103
45476 53988
42692 16285
17169 4001
23321 935
41892 8086
46236 15394
679 21542
26763 36111
47813 62044
22621 35997
6381 14778
17034 21699
54381 53287
35694 34830
14902 30504
5158...

output:

440039161

result:

ok single line: '440039161'

Test #13:

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

input:

2
2 1

output:

3

result:

ok single line: '3'

Test #14:

score: 0
Accepted
time: 79ms
memory: 32176kb

input:

131072
51230 116074
14356 18985
97302 87862
20350 65669
81694 54472
94257 44656
77121 118912
81235 115171
106881 104061
82683 25663
68305 12450
29336 62646
32572 74421
102407 112028
122054 79222
70569 123539
8651 78501
204 34510
69520 18129
55082 68106
51505 114323
100795 60383
61023 59864
57018 337...

output:

776456918

result:

ok single line: '776456918'

Test #15:

score: 0
Accepted
time: 187ms
memory: 61012kb

input:

262144
131863 89153
74747 38646
187112 232634
203855 116743
1197 3109
104299 20430
195824 110378
144817 150658
187558 66008
261366 71448
227156 246386
4149 219771
47465 87425
185952 150310
20653 103389
4917 221350
124004 104544
162181 144076
79557 176106
88679 240655
234082 52601
205629 150797
20194...

output:

777533279

result:

ok single line: '777533279'

Test #16:

score: 0
Accepted
time: 225ms
memory: 158848kb

input:

300000
200042 33358
146127 282853
18162 208274
88763 197176
219535 47504
18973 156413
135038 231317
236314 79984
54777 75970
263068 185590
178314 16697
46633 171708
244101 108105
262612 237866
278911 257361
223742 114478
189208 195065
226678 182830
43889 137857
43488 17945
129846 57509
272492 132190...

output:

528233774

result:

ok single line: '528233774'

Test #17:

score: 0
Accepted
time: 228ms
memory: 121684kb

input:

300000
176764 78952
106987 49376
199197 145137
284233 133549
153566 146492
192389 171608
126109 165447
243592 22382
235466 121116
184443 97521
282334 9814
156 188663
107376 36037
157844 51710
62907 257468
246294 216846
219236 183284
216849 220858
269297 95886
219479 273154
165259 18296
162990 56046
...

output:

750813860

result:

ok single line: '750813860'

Test #18:

score: 0
Accepted
time: 212ms
memory: 99692kb

input:

300000
158309 149704
128435 163070
84245 49253
264263 44739
68743 180951
108361 147453
240926 297856
89945 260111
277457 169826
291582 125079
277648 144954
101400 245176
23891 241280
63493 241546
201991 83439
148391 183664
21371 262320
204841 29292
277535 194623
82560 91044
150547 79025
123803 68605...

output:

580868875

result:

ok single line: '580868875'

Test #19:

score: 0
Accepted
time: 208ms
memory: 80956kb

input:

300000
199668 175926
193518 215061
170371 258103
194712 162222
88766 94800
184812 295037
168857 181854
69199 242470
1818 80752
69395 194806
57376 42758
141192 88538
33986 256933
69427 76218
185239 91491
285920 41676
51905 1936
239856 132282
227388 41622
272706 124375
32038 284692
135219 69014
34936 ...

output:

381083020

result:

ok single line: '381083020'

Test #20:

score: 0
Accepted
time: 859ms
memory: 73320kb

input:

300000
67567 276022
264241 227037
38178 145820
228201 233793
98899 138819
98797 261326
115390 242282
211578 259087
45319 276116
122811 28871
50088 69991
37258 200859
136470 175283
260338 91948
67384 212375
40231 149234
232658 26091
154421 76753
112123 10499
206637 278186
61238 227139
159931 11377
15...

output:

526946130

result:

ok single line: '526946130'

Test #21:

score: 0
Accepted
time: 222ms
memory: 99516kb

input:

300000
298283 154255
105673 91459
90712 551
123440 38867
273284 278037
289955 200645
67178 171102
262920 263155
13243 20544
3484 121690
144944 96882
36832 165786
136889 268839
113999 205529
215711 155237
265165 11117
297845 242471
256546 75078
105444 191232
129806 32926
47865 212371
242475 12162
140...

output:

454830106

result:

ok single line: '454830106'

Test #22:

score: 0
Accepted
time: 252ms
memory: 76820kb

input:

300000
255425 265169
133485 277287
76214 259004
64909 31394
38195 194625
113083 60995
114801 95891
252179 236591
174951 140502
120096 268047
112333 255250
40951 239609
183553 195051
267304 249424
251541 179061
141939 127130
185987 132693
168331 40484
168910 263246
133239 174144
98110 219653
71323 58...

output:

7085656

result:

ok single line: '7085656'

Test #23:

score: 0
Accepted
time: 288ms
memory: 71812kb

input:

300000
231673 112053
254937 146031
82044 136077
65848 14401
248803 96417
78006 18885
141370 451
117569 281482
106784 22636
276187 72289
42145 271720
31090 107912
4141 157651
83282 122287
145094 83114
43582 186660
256861 15404
236538 287383
243614 211230
151496 85034
38002 36984
2314 240792
193219 10...

output:

877977717

result:

ok single line: '877977717'

Test #24:

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

input:

3
1 3
1 2

output:

5

result:

ok single line: '5'

Test #25:

score: 0
Accepted
time: 344ms
memory: 69816kb

input:

299996
296442 185267
50530 274959
28270 115154
148934 249346
160551 84859
233979 154571
22843 135379
230333 236666
298334 183640
92347 194511
173381 25598
266261 136089
287505 185015
146778 296343
66934 86330
153692 167515
208193 268597
182346 21400
267740 194767
257287 155399
234463 206144
132725 4...

output:

958748728

result:

ok single line: '958748728'

Test #26:

score: 0
Accepted
time: 415ms
memory: 69316kb

input:

299997
69620 286151
83759 122458
150200 40713
27544 54012
96245 59812
180550 99731
217930 120974
163696 30804
275834 168480
207497 230467
132307 225351
20315 288360
29579 521
199710 78596
245633 262159
274256 35936
86684 131322
261721 211569
195864 72963
280835 83850
183385 296530
294024 176405
4753...

output:

384944882

result:

ok single line: '384944882'

Test #27:

score: 0
Accepted
time: 543ms
memory: 69376kb

input:

299996
148922 127667
277673 197441
29052 20205
142405 266143
108859 287840
211351 181923
203021 23645
77544 40249
166846 291754
250262 146814
142031 39641
38402 279245
170977 184733
154573 124357
14071 146937
212153 285641
1200 73289
56741 83581
142675 90910
34133 76301
63971 24486
180535 141586
268...

output:

971339277

result:

ok single line: '971339277'

Test #28:

score: 0
Accepted
time: 666ms
memory: 69612kb

input:

300000
25217 119027
159658 129611
152346 126715
76257 239862
233425 241260
187090 97105
81341 83145
30473 53950
155583 160833
167171 33346
34676 267326
225722 210758
237341 282776
212099 153785
193336 57133
276500 78517
85066 68912
97119 251080
56196 52211
226615 249598
251391 205606
246132 131565
3...

output:

871187616

result:

ok single line: '871187616'

Test #29:

score: 0
Accepted
time: 828ms
memory: 71196kb

input:

300000
102824 264542
97459 294443
207887 24517
86542 159734
258999 26536
50082 269866
238475 32007
93949 298385
228703 85982
137498 128652
255827 78235
283491 173194
73700 144605
220086 281986
132744 8302
144861 107759
79676 170516
170650 203290
127771 293088
132201 132047
79581 216013
181179 266867...

output:

99010450

result:

ok single line: '99010450'

Test #30:

score: 0
Accepted
time: 762ms
memory: 73344kb

input:

299996
242479 24995
122936 54434
10553 59084
232524 82036
297620 237283
237495 230131
251637 161635
241458 127410
230096 186466
125271 158610
63285 152286
118009 247683
83334 100530
74546 44699
62150 141585
239718 190019
107197 156126
61127 250943
226268 25100
85759 293768
217704 271966
38189 44651
...

output:

7871987

result:

ok single line: '7871987'

Test #31:

score: 0
Accepted
time: 305ms
memory: 69744kb

input:

300000
141120 87300
194322 170645
229819 142275
41425 298988
299047 109602
88400 186578
26657 236944
254960 49349
81333 19904
154061 156416
159858 5611
23618 127658
267627 222399
129713 170839
32424 220570
79761 69615
23754 150751
159615 217322
217327 16059
128031 112745
216426 255856
7377 182023
17...

output:

800979809

result:

ok single line: '800979809'

Test #32:

score: 0
Accepted
time: 214ms
memory: 69612kb

input:

300000
187459 276511
13204 112858
283815 276191
216613 271575
141969 92717
192257 110307
201403 277104
230595 155995
97518 49107
196198 299078
44975 1963
263278 272852
13453 8890
287918 22659
178192 78528
164812 271085
83986 14827
32133 247475
125396 3364
154483 90786
176446 208266
109982 172113
241...

output:

808644428

result:

ok single line: '808644428'

Test #33:

score: 0
Accepted
time: 189ms
memory: 69432kb

input:

299996
188752 101719
279316 246986
234432 243419
272970 705
38885 125692
240413 78732
273782 184744
211520 114706
90561 155300
15819 98642
155001 197334
176234 106386
230375 27141
159458 105976
43931 251797
277213 32451
178296 156807
3676 281605
157162 90450
60940 129806
130286 169475
285884 289386
...

output:

379195932

result:

ok single line: '379195932'

Test #34:

score: 0
Accepted
time: 455ms
memory: 123884kb

input:

300000
237729 123037
157430 246971
184400 158079
30617 11884
31953 246475
131242 106766
264888 224761
125361 26673
60635 106163
160321 262774
230455 159426
140331 83773
155773 191180
158116 83790
67422 218479
261855 78986
252389 128069
15587 19850
206767 152122
45054 44339
253201 270428
42310 112952...

output:

519652329

result:

ok single line: '519652329'

Test #35:

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

input:

4
1 4
2 3
3 4

output:

13

result:

ok single line: '13'

Test #36:

score: 0
Accepted
time: 509ms
memory: 106232kb

input:

300000
11262 192408
116072 24230
187003 272190
273685 210077
170965 38577
194980 295045
33802 190819
64796 200244
15854 4901
202070 198383
290577 17054
107551 141242
136681 75729
227834 27837
83600 69127
15544 192976
155253 272248
30643 269233
239057 254976
220514 163342
127578 161160
237442 44536
2...

output:

412009401

result:

ok single line: '412009401'

Test #37:

score: 0
Accepted
time: 462ms
memory: 82716kb

input:

299996
109754 77210
195890 236220
252772 122307
44379 284046
257265 245023
201955 113521
274770 82921
236926 282039
30764 7873
248940 138345
94397 171146
218010 228599
89329 5521
98515 247653
142110 275931
89149 206620
219431 221691
220173 140322
267768 192657
17204 134951
157598 243149
65102 174137...

output:

896924076

result:

ok single line: '896924076'

Test #38:

score: -100
Time Limit Exceeded

input:

299999
126262 52144
78038 52144
52144 71458
218142 43724
185628 234525
37447 36821
119760 217021
148818 187846
52144 227498
169948 52144
65195 219140
120149 264074
183247 135413
77629 109688
88071 52144
268556 52144
94175 52144
52144 155393
52144 48570
264251 211414
4769 52144
155619 13823
119908 52...

output:


result: