QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#644148 | #9346. Binary Numbers | planckconstant | AC ✓ | 184ms | 374016kb | C++14 | 1.5kb | 2024-10-16 11:16:34 | 2024-10-16 11:16:34 |
Judging History
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