QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #706421 | #9464. 基础 01? 练习题 | Aaronwrq# | 20 | 2511ms | 331072kb | C++14 | 2.3kb | 2024-11-03 11:14:27 | 2024-11-03 11:14:28 |
Judging History
answer
#include <bits/stdc++.h>
#define MAXN 4010
using namespace std;
int n, m, q, ck[MAXN], po2[MAXN];
string S, T;
int hpo[MAXN][2], hp[2] = {131, 13331}, hm[2] = {998244353, 1000000007};
int s[MAXN][MAXN];
unordered_map<long long, bool> mp;
const int mod = 998244353, i2 = (mod + 1) >> 1;
void Addc(long long &nowh0, long long &nowh1, int c) {
nowh0 = (nowh0 * hp[0] + c) % hm[0];
nowh1 = (nowh1 * hp[1] + c) % hm[1];
return;
}
void dfs(const int p) {
if (p >= n) {
long long nowh0 = 0, nowh1 = 0;
for (int i = 0, j = -1; i < n; ++i) {
while (j < i) ++j, Addc(nowh0, nowh1, S[j]);
while (j < n - 1) {
long long newh0 = nowh0, newh1 = nowh1;
Addc(newh0, newh1, S[j + 1]);
if (mp[(newh0 << 30) | newh1]) ++j, nowh0 = newh0, nowh1 = newh1;
else break;
}
++s[i][i], --s[i][j + 1];
nowh0 = (nowh0 + 1ll * (hm[0] - hpo[j - i][0]) * S[i]) % hm[0];
nowh1 = (nowh1 + 1ll * (hm[1] - hpo[j - i][1]) * S[i]) % hm[1];
}
return;
}
if (S[p] != '?') dfs(p + 1);
else {
S[p] = '0', dfs(p + 1);
S[p] = '1', dfs(p + 1);
S[p] = '?';
}
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> q >> S;
T = "0", m = n << 2;
for (int i = 1; i < m; ++i) T += T[i >> 1] ^ (i & 1);
hpo[0][0] = hpo[0][1] = 1;
for (int i = 1; i < m; ++i) {
hpo[i][0] = 1ll * hpo[i - 1][0] * hp[0] % hm[0];
hpo[i][1] = 1ll * hpo[i - 1][1] * hp[1] % hm[1];
}
for (int i = 0; i < n; ++i) ck[i] = S[i] == '?';
for (int i = 1; i < n; ++i) ck[i] += ck[i - 1];
po2[0] = 1;
for (int i = 1; i <= n; ++i) po2[i] = 1ll * po2[i - 1] * i2 % mod;
for (int i = 0; i < m; ++i) {
long long nowh0 = 0, nowh1 = 0;
for (int j = i; j < m; ++j) {
Addc(nowh0, nowh1, T[j]);
mp[(nowh0 << 30) | nowh1] = 1;
}
}
dfs(0);
for (int i = 0; i < n; ++i) for (int j = 1; j < n; ++j) s[i][j] += s[i][j - 1];
for (int i = 0; i < n; ++i) for (int j = 1; j < n; ++j) s[i][j] = (s[i][j] + s[i][j - 1]) % mod;
for (int i = 1; i < n; ++i) for (int j = 0; j < n; ++j) s[i][j] = (s[i][j] + s[i - 1][j]) % mod;
while (q--) {
int l, r; cin >> l >> r;
int ans = s[n - 1][r], cc = ck[r];
if (l) ans = (ans + mod - s[l - 1][r]) % mod, cc -= ck[l - 1];
cout << 1ll * ans * po2[ck[n - 1] - cc] % mod << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1ms
memory: 5796kb
input:
15 15 0???0??01???1?? 2 14 0 9 6 10 1 14 1 14 0 12 5 14 6 7 0 6 4 14 1 12 10 10 0 14 1 12 4 7
output:
25883 2344 112 56425 56425 12963 4531 6 666 5212 11875 2 60786 11875 37
result:
ok 15 numbers
Test #2:
score: 10
Accepted
time: 1ms
memory: 3668kb
input:
15 15 011?1?0101??110 0 11 2 10 0 13 2 12 3 5 2 12 3 5 12 13 1 14 1 5 8 13 9 12 2 10 0 11 7 8
output:
803 285 952 732 23 732 23 3 940 48 69 37 285 803 3
result:
ok 15 numbers
Test #3:
score: 10
Accepted
time: 1ms
memory: 3624kb
input:
15 15 100110?1010?01? 9 9 6 11 1 4 0 13 7 7 9 13 3 14 0 0 0 13 0 12 0 10 6 11 4 8 3 13 0 13
output:
1 77 10 265 1 25 384 1 265 251 109 77 30 175 265
result:
ok 15 numbers
Test #4:
score: 10
Accepted
time: 4ms
memory: 3760kb
input:
15 15 ??????0?0?????? 8 10 0 14 9 12 2 13 1 6 7 12 0 13 6 14 0 11 0 14 4 14 5 14 0 8 4 5 1 13
output:
23 439848 146 41764 540 540 202272 3703 41802 439848 18776 8386 3703 12 92312
result:
ok 15 numbers
Test #5:
score: 10
Accepted
time: 1ms
memory: 3732kb
input:
15 15 ?1??0?0??010?1? 3 14 4 5 0 14 0 13 4 8 12 13 1 5 5 8 11 13 3 3 1 12 0 2 5 14 11 12 4 12
output:
3128 6 15531 6994 99 6 101 73 12 2 2842 23 1305 6 522
result:
ok 15 numbers
Test #6:
score: 10
Accepted
time: 1ms
memory: 3756kb
input:
15 15 10????1001?11?1 0 14 0 5 0 14 5 13 4 9 10 14 6 13 0 14 1 9 0 13 6 13 1 11 1 13 9 13 4 5
output:
4184 279 4184 276 78 46 109 4184 531 3878 109 1446 3516 46 12
result:
ok 15 numbers
Subtask #2:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 43ms
memory: 3988kb
input:
20 200000 ???10?10???????1???? 1 19 2 17 5 19 6 19 6 15 5 19 1 11 0 15 4 6 3 16 10 13 12 18 16 16 0 15 7 14 2 11 14 19 9 16 0 18 11 16 7 13 1 17 5 18 7 7 6 10 4 17 5 19 2 9 0 16 1 19 5 14 4 19 0 11 0 16 15 19 0 12 1 15 4 17 13 16 3 14 4 13 5 13 3 10 0 19 2 17 6 18 0 18 7 10 3 18 10 14 1 13 0 16 0 19...
output:
1336706 138392 234942 106457 4426 234942 5914 141418 12 28991 146 1346 2 141418 3235 2622 540 3235 1346550 540 1346 298458 108555 1 107 55692 234942 504 300854 1336706 9100 258457 13090 300854 206 28541 65634 55692 73 12242 4720 3994 479 2835902 138392 48773 1346550 73 133840 412 28291 300854 283590...
result:
wrong answer 1st numbers differ - expected: '1336712', found: '1336706'
Subtask #3:
score: 0
Runtime Error
Test #13:
score: 0
Runtime Error
input:
50000 200000 011001101001011?10011001011010010110011010011001011?011010010110?0011001011001101?011?010?10100101100110100110010110011?1001011010011001011?10010?1?0?10100101101?01100101100110100110010110?001011001101001100101100?10100101101?0110?10110011010011001011010010110011010010110100110?10110100...
output:
result:
Subtask #4:
score: 0
Runtime Error
Test #19:
score: 0
Runtime Error
input:
50000 1 0101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010011001011001101001011010011001011010010110011010010110100110010110011010011001011010...
output:
result:
Subtask #5:
score: 0
Runtime Error
Test #25:
score: 0
Runtime Error
input:
50000 1 01011010011000110100110010110010?1001?0001011001101?001011001101?0101101?011011001101001010?10100101101001100101?01100101010?101001100110?1011010011001011010??110011?1?011001?1100110?101101001100101100100110010110011100110100101001?1?0?00?100101101001011001101001011100?1010010110101101001011...
output:
result:
Subtask #6:
score: 5
Accepted
Test #31:
score: 5
Accepted
time: 381ms
memory: 82828kb
input:
500 1000 011000100010010010010010110010101100101100101011010010011001101001011010011000010011010001011010000001100101100110100101101001001011010010110010110100101100111001100111010011010010110100110010110100101100110101000101100110100110010110100101100110100101101?01101101100101011001010010100110010...
output:
399 1770 1496 922 2273 23256 14888 21468 5050 11956 7336 16724 1640 23288 23076 5699 23296 556 10300 23036 2274 14904 344 958 8912 1922 372 16048 14908 2830 20496 748 17988 22832 21300 22324 17996 23792 3 17104 19492 474 8664 14960 19820 339 1402 12048 24060 20344 19324 20304 5254 3962 20340 1532 52...
result:
ok 1000 numbers
Test #32:
score: 5
Accepted
time: 385ms
memory: 82692kb
input:
500 1000 0010100100010011011101100101000010010110100101101001010010110101001?1001?0100100010010100010110110010111101110110001010010001011001010001010001001100101010011010110100110101111001001010101101000101100101100111011110110100100011010?101110010101111000101010000001110011010011000101100100101100...
output:
137 2544 479 2586 2756 19644 43352 2768 2692 12260 7068 92416 810 28 17768 91888 15836 15220 2618 327 3972 139 1504 7832 1069 12668 2576 45752 8904 2500 2582 94864 10356 95856 3446 15260 492 17572 15 43144 116 2898 81456 1738 3482 1130 4416 216 473 16884 2130 17812 39408 46312 3 2184 2774 224 7792 6...
result:
ok 1000 numbers
Test #33:
score: 5
Accepted
time: 389ms
memory: 82772kb
input:
500 1000 101001001?11011010010111100110010110101010010001111?10101010001101011011001110100101110011010011101011101110110100101011000001000110110000101000010010011?0100100100010001010001010011010011010001?011010011001110110101101011110100011100100101110011011010110101101010110100001101001110000101101...
output:
11024 63280 293632 2683 21432 712 3282 26296 3014 51856 3280 319520 156 19816 150912 1655 4506 675776 1212 2286 17620 1130 1066 28424 2306 9816 8080 2014 128320 11132 658880 740 324 2986 316832 678848 2560 4204 65440 2118 1138 5146 26664 64880 188 7392 1 145808 20808 568 9720 8996 6648 70352 35 1175...
result:
ok 1000 numbers
Test #34:
score: 5
Accepted
time: 368ms
memory: 82764kb
input:
500 1000 11010011001101101001011010110010100110110110?01001110101001010100111?010110011001001001101001110100101001100101101001001001101101001111100110100110010110011101100000100110111010001010011001101001011?1110011011101010010111001101101101101001010010001001011011001?010011001011110010?1100101?011...
output:
17104 869248 19664 56 198080 5168 12128 165472 65488 10 2716 913 385472 885248 50608 585 1760 14 356416 27440 185888 72336 1311 1794 438080 417472 1995 224 56432 270400 978 619 170624 402048 371520 416704 409728 85072 333632 1749 67568 26992 314688 1073 417216 406464 317248 897920 826368 52688 89459...
result:
ok 1000 numbers
Test #35:
score: 5
Accepted
time: 366ms
memory: 82612kb
input:
500 1000 01100011001011011100101100110100110010110100010011010110011010010010110100100110010011001011001101001011001101001?110100101100011010011001011001101001011011?01001011010000101100110100101101100110101100110100101101001100101100110010110011011000011011001011000011010010110100101100111001011001...
output:
165248 67 67800 12312 6642 173728 129888 3724 44680 59112 343 2285 2628 356640 5150 74520 651 7544 2299 23680 32548 3908 3919 337952 682 119008 123024 276 13148 33452 8254 70552 7082 799 10000 734 170048 367136 1470 398 2127 14100 763 182688 350560 804 62088 10108 365472 16168 11136 66 2347 56664 15...
result:
ok 1000 numbers
Test #36:
score: 5
Accepted
time: 391ms
memory: 82668kb
input:
500 1000 0110100110010110100101?00110100101101001100101100101101001100101100110100110010110101001011001101010100?100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001100?0110011010110100110010110011010010110?001100101100110?001100101...
output:
393 233816 97288 178160 157752 521488 7155 2230 429616 78500 29384 192248 13936 22126 1952 103352 547504 165400 722032 39936 6616 1335584 3086016 65036 278 91692 619024 96060 62792 198512 642160 20596 627120 16676 1248096 356616 4303 79340 229120 570368 28 5047 11090 36716 1276320 1454432 17460 1160...
result:
ok 1000 numbers
Subtask #7:
score: 5
Accepted
Test #37:
score: 5
Accepted
time: 2485ms
memory: 330904kb
input:
1000 2000 01100101101001011001101001011010011001011010010110011010011001011001101001011010011001011010010110011010000110100101101001100101100110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100101101001100101101001011001101001...
output:
3240 660160 644768 11858784 5776 12121 11513184 618368 615968 283884 287756 131958 136654 688720 16592 16444 585256 11476064 5050 591504 106490 114470 137158 1596 6031 5648304 11535200 111930 4278 11445472 51501 11529312 1770 50069 137226 8806 139654 5686 1891 22402 19931 138610 107750 51709 117090 ...
result:
ok 2000 numbers
Test #38:
score: 5
Accepted
time: 2465ms
memory: 330836kb
input:
1000 2000 010000101101000010011011001?111011010010101100110010110010010110011001011011110010111001011011001001110100101100110100000100110100100110110010101100110100110101100110100110010110010101101001100010011010101011010010100110?001001101110010110100100101011010011101001111110100110011010101011001...
output:
36508 1032896 1090624 6 9394 1164 216576 987968 6772 1376 21 26580 2206 39060 1938 2464 1002560 36308 3094 1063744 3042 39804 26020 3234 988480 34740 40740 2380 1100224 718 1063744 1060800 451648 34076 7342 3308 21716 9366 2066 38796 37828 463680 491392 473984 214720 26916 453824 24692 1027392 1702 ...
result:
ok 2000 numbers
Test #39:
score: 5
Accepted
time: 2468ms
memory: 331072kb
input:
1000 2000 0110100011010011001011100?01111010011001011001001011010100011001100100?011000011001011001101001011010011011001011100101100110100101101001100101100110100110010110100101110100110100110100110010011001011010001010100110010110011001100101101001010110100101010101001100101100101001011001101001100...
output:
989 34652 26512 40236 53876 51268 54464 54508 56676 33632 11404 17288 5168 34224 127692 42724 27324 917 59220 54360 45664 127748 39988 10760 55776 31204 54428 18512 51836 53996 122368 8964 125652 31764 3520 42364 41944 711 127780 127164 4244 45848 54996 3 123124 44644 11488 57544 51016 17984 30840 3...
result:
ok 2000 numbers
Test #40:
score: 5
Accepted
time: 2500ms
memory: 330944kb
input:
1000 2000 01100110100110010110100101100110100101101001100001011010010110011010010110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110011010010110100110010110011010011001011010010110011010011001011001100101101001101001011010011001011010010110011010...
output:
231 2210 13703 1672512 55498 1907568 60184 1886352 261516 1756608 12639 12734 1409072 70520 1541952 11132 1685808 21 284252 11707 2669 1174 1490544 1802544 259548 1917168 2507 227164 9809 261516 332836 1572912 1207 331780 1751664 680576 2782 1913328 1942512 671608 332836 2257 1464624 1873472 1467072...
result:
ok 2000 numbers
Test #41:
score: 5
Accepted
time: 2511ms
memory: 330844kb
input:
1000 2000 1101001100101001100101100110100101101001101100110100110010110011010010110100110010110100101100110100110010110100101101010011001011010001011001101001011010011001011010010011010010110011010010110010110100110010100110010110100101100110100110010110011010011?010110011010010110100110010110011010...
output:
4543 4732 134104 68168 2925 116176 133168 691200 114720 126656 4421 110752 1490496 324576 98536 114664 62472 3501 75488 129424 89408 29512 13318 91 123344 126504 100 205 60480 27052 128632 131200 1587456 1678656 83848 704832 69608 5263 128648 1457856 4577 128424 120936 1451968 705728 296032 1618368 ...
result:
ok 2000 numbers
Test #42:
score: 5
Accepted
time: 2491ms
memory: 330936kb
input:
1000 2000 00101101001011001101001011010011001011010?1011001101001100?01100110100101101001100101101?0101100110100101101001101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100010110100101100110100?1001011001101001011010011001011010010110011010010...
output:
34744992 4054912 38220 506120 8568032 4141440 4143808 3505952 800000 1927232 73860 17225056 31668 2151632 8740 19180 630 25944 4097440 2528896 629960 3380600 26564 815096 2068240 20092 34597920 3882640 34679232 34620 2037496 4066240 36092128 3244360 4002896 351 35317408 171072 178176 1755152 6892 35...
result:
ok 2000 numbers
Subtask #8:
score: 0
Runtime Error
Test #43:
score: 0
Runtime Error
input:
5000 100000 ????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
result:
Subtask #9:
score: 0
Runtime Error
Test #49:
score: 0
Runtime Error
input:
20000 100000 ????????????????????????????0??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
result:
Subtask #10:
score: 0
Runtime Error
Test #55:
score: 0
Runtime Error
input:
50000 200000 ?01101001011001?01?011?010?1001101001?110?001?0?1?1?001101?0110?101?010??01100110?00?1001011001101001011??001?001?110100101100110100101?01?0110?1011?011010011001?1?0100??110011?100?01101001100?011010?10??00110100?1?0?0110?1101?01??1?10??10010?10?00101?00??0???101101?0???010110??1?10011?...