QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#644148#9346. Binary NumbersplanckconstantAC ✓184ms374016kbC++141.5kb2024-10-16 11:16:342024-10-16 11:16:34

Judging History

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

  • [2024-10-16 11:16:34]
  • 评测
  • 测评结果:AC
  • 用时:184ms
  • 内存:374016kb
  • [2024-10-16 11:16:34]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=100000007;
ll dp[(1<<19)][19][19];
void solve()
{
    int n,m;
    cin>>m>>n;
    vector<pair<int,int>>a(n+5);
    for(int i=1;i<=n;i++){
        cin>>a[i].first>>a[i].second;
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            for(int k=0;k<=m;k++){
                dp[i][j][k]=0;
            }
        }
    }
    dp[0][m][0]=1;
    auto get_lca=[m](int a,int b)->int{
        int ans=0;
        for(int i=m-1;i>=0;i--){
            if((a>>i)^(b>>i)){
                break;
            }
            ans++;
        }
        return ans;
    };
    for(int i=1;i<=n;i++){
        for(int j=a[i].first;j<=a[i].second;j++){
            int k1=get_lca(j,a[i].second);
            int k2=m;
            if(i!=n)
                k2=get_lca(j,a[i+1].first);
            int k3=get_lca(j,a[i].first);
            int k4=0;
            if(i!=1)
                k4=get_lca(j,a[i-1].second);
            for(int k=0;k<=m;k++){
                for(int o=0;o<=m;o++){
                    if(k4<=k&&k3>=o){
                        dp[i][k1][k2]=(dp[i][k1][k2]+dp[i-1][k][o]*j%mod)%mod;
                    }
                }
            }
        }
    }
    ll re=0;
    for(int i=0;i<=m;i++){
        re=(re+dp[n][i][m])%mod;
    }
    cout<<re<<'\n';
}
signed main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin >> T;
    while(T--) solve();
    return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

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

input:

1
2 2
0 1
2 3

output:

5

result:

ok single line: '5'

Test #2:

score: 0
Accepted
time: 97ms
memory: 90728kb

input:

20
4 6
0 1
2 3
4 6
7 7
8 11
12 15
9 39
0 31
32 47
48 51
52 63
64 87
88 92
93 95
96 127
128 143
144 159
160 167
168 175
176 191
192 207
208 255
256 263
264 271
272 283
284 287
288 289
290 295
296 303
304 319
320 351
352 357
358 367
368 375
376 383
384 391
392 399
400 403
404 407
408 415
416 443
444 4...

output:

430920
27651757
80424846
87716714
4008233
5040
28188720
87385831
28330657
91763968
65697486
23193906
2268
73598267
1
16867205
48893476
83201790
28
54705494

result:

ok 20 lines

Test #3:

score: 0
Accepted
time: 51ms
memory: 3740kb

input:

20
11 43
0 95
96 111
112 127
128 255
256 351
352 383
384 447
448 511
512 543
544 575
576 639
640 735
736 767
768 895
896 899
900 959
960 975
976 991
992 1023
1024 1151
1152 1215
1216 1239
1240 1247
1248 1279
1280 1407
1408 1439
1440 1463
1464 1535
1536 1663
1664 1791
1792 1823
1824 1839
1840 1855
18...

output:

84091164
45591833
72625155
28
55368141
58996981
65566900
57365327
5
44545690
2396038
37853636
34640508
35600827
21626271
42840
6
7982056
95927916
2766679

result:

ok 20 lines

Test #4:

score: 0
Accepted
time: 81ms
memory: 20640kb

input:

20
1 1
0 1
1 1
0 1
3 6
0 1
2 2
3 3
4 4
5 5
6 7
16 3552
0 13
14 63
64 79
80 95
96 127
128 191
192 195
196 223
224 255
256 331
332 335
336 351
352 359
360 383
384 511
512 607
608 639
640 671
672 703
704 767
768 799
800 815
816 831
832 895
896 983
984 991
992 1023
1024 1087
1088 1103
1104 1151
1152 121...

output:

1
1
1560
94919655
58229969
84885385
1
13770462
5776789
6
6
30525183
10886980
38928251
93365188
327600
9383058
49652475
1
6

result:

ok 20 lines

Test #5:

score: 0
Accepted
time: 31ms
memory: 3488kb

input:

20
10 8
0 63
64 127
128 255
256 511
512 607
608 639
640 767
768 1023
16 9
0 24575
24576 27135
27136 28671
28672 32767
32768 33791
33792 49151
49152 58367
58368 61439
61440 65535
2 3
0 1
2 2
3 3
5 9
0 3
4 5
6 7
8 15
16 17
18 19
20 21
22 23
24 31
7 2
0 63
64 127
3 5
0 1
2 2
3 3
4 6
7 7
8 2
0 127
128 2...

output:

69771922
40505947
6
80037040
12321792
252
99233529
5040
65089440
210
2096128
27552313
1
6
69521310
1890
29356571
20
98433882
41735733

result:

ok 20 lines

Test #6:

score: 0
Accepted
time: 39ms
memory: 16724kb

input:

100
10 137
0 7
8 15
16 31
32 39
40 43
44 47
48 51
52 63
64 79
80 95
96 99
100 103
104 111
112 115
116 117
118 119
120 127
128 131
132 135
136 137
138 143
144 159
160 163
164 167
168 175
176 183
184 191
192 215
216 223
224 227
228 231
232 233
234 235
236 239
240 251
252 253
254 255
256 271
272 283
28...

output:

53200371
132
120
0
23070158
27408481
25882500
0
0
0
0
69797223
28
92867065
0
20190671
0
94075954
69532351
0
65318706
0
13732130
28
98983631
0
11910059
29577315
6
29123932
25848084
92590601
0
0
132
88885328
12955848
88915375
24821676
0
68212605
89949280
0
5
50062718
16741407
0
6
1
0
0
0
0
0
49232956
...

result:

ok 100 lines

Test #7:

score: 0
Accepted
time: 40ms
memory: 16408kb

input:

100
5 16
0 2
3 3
4 5
6 6
7 15
16 16
17 17
18 18
19 19
20 21
22 23
24 25
26 27
28 28
29 29
30 31
11 1641
0 1
2 2
3 3
4 5
6 6
7 7
8 8
9 9
10 10
11 11
12 13
14 14
15 15
16 17
18 18
19 19
20 20
21 21
22 23
24 25
26 27
28 28
29 29
30 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 41
42 42
43 43
44...

output:

10398635
86706294
25525993
702
42329680
81237162
36087286
56264174
28
51318718
3558275
69420459
110
225720
99058729
53066672
65171781
89758497
91966648
1
92886935
1
6
65815728
56242796
24954661
37982897
16742085
74276468
300688
1
5040
1
33598882
92097427
1
22804325
43466333
34389231
74276468
496
1
5...

result:

ok 100 lines

Test #8:

score: 0
Accepted
time: 180ms
memory: 45516kb

input:

20
14 241
0 127
128 255
256 287
288 319
320 383
384 447
448 465
466 479
480 487
488 511
512 655
656 703
704 767
768 783
784 793
794 799
800 895
896 1023
1024 1087
1088 1127
1128 1151
1152 1279
1280 1535
1536 1727
1728 1767
1768 1791
1792 1991
1992 2015
2016 2047
2048 2255
2256 2271
2272 2303
2304 23...

output:

23566590
31968154
6
89235481
54088114
70518405
70152387
48069527
74276468
1560
91551100
28494833
4200
59015472
25398222
56433442
36829034
52266800
75155166
46054251

result:

ok 20 lines

Test #9:

score: 0
Accepted
time: 130ms
memory: 16624kb

input:

20
11 664
0 1
2 3
4 7
8 9
10 10
11 11
12 13
14 15
16 18
19 19
20 20
21 21
22 23
24 24
25 27
28 31
32 35
36 36
37 39
40 41
42 43
44 45
46 47
48 53
54 55
56 57
58 59
60 63
64 65
66 67
68 71
72 75
76 77
78 79
80 81
82 83
84 87
88 91
92 93
94 95
96 99
100 103
104 107
108 111
112 113
114 115
116 127
128 ...

output:

15510250
5
43833619
4686092
96004971
41071083
702
73106880
53717300
40818000
1
74276468
88962949
6
86396842
91340161
70990107
3934400
72006011
51589826

result:

ok 20 lines

Test #10:

score: 0
Accepted
time: 140ms
memory: 6616kb

input:

20
5 10
0 7
8 8
9 9
10 11
12 15
16 23
24 24
25 27
28 29
30 31
3 5
0 3
4 4
5 5
6 6
7 7
4 15
0 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 217
0 2047
2048 4095
4096 4607
4608 5119
5120 5375
5376 6143
6144 6399
6400 6655
6656 6927
6928 7167
7168 8191
8192 9215
9216 9727
972...

output:

11515463
5040
74276468
96116762
702
88919625
6
19157473
1444320
55660414
55409756
1
15817535
85063739
74607834
71680851
15361372
34593885
57958381
899937

result:

ok 20 lines

Test #11:

score: 0
Accepted
time: 82ms
memory: 3608kb

input:

20
12 4
0 2047
2048 2303
2304 2559
2560 4095
13 9
0 511
512 1023
1024 2047
2048 4095
4096 5759
5760 6143
6144 6655
6656 7167
7168 8191
4 5
0 7
8 9
10 10
11 11
12 15
2 3
0 1
2 2
3 3
8 5
0 31
32 63
64 75
76 127
128 255
7 1
0 127
2 3
0 1
2 2
3 3
9 3
0 127
128 255
256 511
7 7
0 31
32 63
64 91
92 95
96 1...

output:

90240804
88278858
2827440
6
14926350
8128
6
50261143
80201661
32897080
33550336
49724311
97251995
539784
30328877
25430613
95557798
22706642
89592198
6

result:

ok 20 lines

Test #12:

score: 0
Accepted
time: 98ms
memory: 41460kb

input:

100
2 4
0 0
1 1
2 2
3 3
2 4
0 0
1 1
2 2
3 3
10 601
0 1
2 2
3 3
4 4
5 5
6 7
8 8
9 9
10 11
12 15
16 16
17 17
18 18
19 19
20 21
22 23
24 24
25 25
26 26
27 27
28 29
30 31
32 32
33 33
34 34
35 35
36 36
37 37
38 39
40 41
42 42
43 43
44 45
46 47
48 48
49 49
50 55
56 57
58 58
59 59
60 60
61 61
62 63
64 64
6...

output:

0
0
77507610
56760252
0
14520042
0
38905214
270864
31370845
0
0
0
76370016
0
0
10764
2268
1
73980691
0
0
93155288
87270761
7287084
0
20931514
0
0
65915450
0
0
2576
0
6
57746031
0
0
0
88454620
0
6
0
0
1
0
0
91922448
0
85414051
0
97043696
81695143
0
67807579
0
39809109
12028366
57329212
21246463
0
692...

result:

ok 100 lines

Test #13:

score: 0
Accepted
time: 136ms
memory: 41316kb

input:

100
3 7
0 0
1 1
2 2
3 3
4 4
5 5
6 7
4 13
0 0
1 1
2 3
4 4
5 5
6 7
8 8
9 9
10 11
12 12
13 13
14 14
15 15
2 1
0 3
9 147
0 7
8 15
16 19
20 22
23 23
24 31
32 37
38 47
48 49
50 51
52 55
56 58
59 59
60 63
64 65
66 71
72 79
80 81
82 83
84 85
86 87
88 91
92 93
94 95
96 103
104 107
108 111
112 115
116 119
120...

output:

0
0
6
73430523
0
508950
12290146
0
23047959
0
0
66483398
83495289
93397620
4118400
56731969
0
0
35571605
49209073
1
1560
0
0
52503296
42912138
0
67753196
63072088
1
0
0
69936067
496
0
34576722
0
13922238
0
41921021
42383302
12443529
0
117
0
6
14077150
64961109
0
73819984
0
34797036
0
1
0
0
252
93005...

result:

ok 100 lines

Test #14:

score: 0
Accepted
time: 116ms
memory: 374016kb

input:

1
17 131072
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40
41 41
42 42
43 43
44 44
45 45
46 46
47 47
48 48
49 49
50 50
51...

output:

0

result:

ok single line: '0'

Test #15:

score: 0
Accepted
time: 160ms
memory: 190664kb

input:

2
16 65536
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40
41 41
42 42
43 43
44 44
45 45
46 46
47 47
48 48
49 49
50 50
51 ...

output:

0
12472103

result:

ok 2 lines

Test #16:

score: 0
Accepted
time: 177ms
memory: 98136kb

input:

3
15 32768
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40
41 41
42 42
43 43
44 44
45 45
46 46
47 47
48 48
49 49
50 50
51 ...

output:

0
8400586
61239618

result:

ok 3 lines

Test #17:

score: 0
Accepted
time: 181ms
memory: 27352kb

input:

5
13 8192
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40
41 41
42 42
43 43
44 44
45 45
46 46
47 47
48 48
49 49
50 50
51 5...

output:

0
71065116
40094294
21561411
32767466

result:

ok 5 lines

Test #18:

score: 0
Accepted
time: 184ms
memory: 10456kb

input:

7
11 2048
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40
41 41
42 42
43 43
44 44
45 45
46 46
47 47
48 48
49 49
50 50
51 5...

output:

0
74891778
18974432
21548749
45421072
83754700
62618533

result:

ok 7 lines

Test #19:

score: 0
Accepted
time: 180ms
memory: 5788kb

input:

9
9 512
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40
41 41
42 42
43 43
44 44
45 45
46 46
47 47
48 48
49 49
50 50
51 51
...

output:

0
70027435
34175906
75910652
59243058
5303741
79633241
32961775
7470220

result:

ok 9 lines

Test #20:

score: 0
Accepted
time: 155ms
memory: 3696kb

input:

12
6 64
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40
41 41
42 42
43 43
44 44
45 45
46 46
47 47
48 48
49 49
50 50
51 51
...

output:

0
93427371
13354912
5141308
65760958
86286092
73920878
5236780
49347942
61868285
72774221
11318819

result:

ok 12 lines

Test #21:

score: 0
Accepted
time: 109ms
memory: 3568kb

input:

15
3 8
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
4 8
0 1
2 3
4 5
6 7
8 9
10 11
12 13
14 15
5 8
0 3
4 7
8 11
12 15
16 19
20 23
24 27
28 31
6 8
0 7
8 15
16 23
24 31
32 39
40 47
48 55
56 63
7 8
0 15
16 31
32 47
48 63
64 79
80 95
96 111
112 127
8 8
0 31
32 63
64 95
96 127
128 159
160 191
192 223
224 255
9 8
0 63
...

output:

0
51412618
15632267
32281473
70065736
80865593
49579927
80538529
63240053
51406921
4762684
86179288
95163395
90585285
97962896

result:

ok 15 lines

Test #22:

score: 0
Accepted
time: 61ms
memory: 3804kb

input:

18
0 1
0 0
1 1
0 1
2 1
0 3
3 1
0 7
4 1
0 15
5 1
0 31
6 1
0 63
7 1
0 127
8 1
0 255
9 1
0 511
10 1
0 1023
11 1
0 2047
12 1
0 4095
13 1
0 8191
14 1
0 16383
15 1
0 32767
16 1
0 65535
17 1
0 131071

output:

0
1
6
28
120
496
2016
8128
32640
130816
523776
2096128
8386560
33550336
34209529
36854493
47450733
89868461

result:

ok 18 lines

Extra Test:

score: 0
Extra Test Passed