QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #706378 | #9464. 基础 01? 练习题 | Aaronwrq# | 0 | 2418ms | 330920kb | C++14 | 2.1kb | 2024-11-03 10:58:21 | 2024-11-03 10:58:22 |
Judging History
answer
#include <bits/stdc++.h>
#define MAXN 4010
using namespace std;
int n, m, q, ck[MAXN];
string S, T;
int hpo[MAXN][2], hp[2] = {131, 13131}, hm[2] = {998244353, 1000000007};
int s[MAXN][MAXN];
unordered_map<long long, bool> mp;
const int mod = 998244353;
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] = hpo[i - 1][0] * hp[0] % hm[0];
hpo[i][1] = 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];
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];
if (l) ans = (ans + mod - s[l - 1][r]) % mod;
cout << ans << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3772kb
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:
23709 25024 6944 27753 27753 29760 14010 2336 17472 16726 25408 1024 32114 25408 6080
result:
wrong answer 1st numbers differ - expected: '25883', found: '23709'
Subtask #2:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 39ms
memory: 3780kb
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:
1151718 929140 606096 528955 396112 606096 867328 1180480 149504 734680 135744 231408 32768 1180480 299552 712192 197203 274344 1281238 200088 265216 1085616 573174 32768 212992 639756 606096 616448 1214600 1151718 438880 705765 1028864 1214600 164126 1071680 1018080 639756 131848 666272 503232 4040...
result:
wrong answer 1st numbers differ - expected: '1336712', found: '1151718'
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: 0
Wrong Answer
Test #31:
score: 0
Wrong Answer
time: 373ms
memory: 82580kb
input:
500 1000 011000100010010010010010110010101100101100101011010010011001101001011010011000010011010001011010000001100101100110100101101001001011010010110010110100101100111001100111010011010010110100110010110100101100110101000101100110100110010110100101100110100101101?01101101100101011001010010100110010...
output:
144 520 596 448 468 1864 1184 1680 660 872 1120 1352 608 1864 1896 748 1900 188 1016 1876 672 1164 136 364 780 604 160 1308 1176 316 1612 236 1472 1860 1696 1784 1504 1960 8 1292 1516 232 656 1192 1540 216 324 988 2036 1584 1632 1572 664 772 1564 368 688 484 792 596 1588 200 1928 804 1336 612 1168 1...
result:
wrong answer 1st numbers differ - expected: '399', found: '144'
Subtask #7:
score: 0
Wrong Answer
Test #37:
score: 0
Wrong Answer
time: 2418ms
memory: 330920kb
input:
1000 2000 01100101101001011001101001011010011001011010010110011010011001011001101001011010011001011010010110011010000110100101101001100101100110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100101101001100101101001011001101001...
output:
829440 1606656 1597184 1651968 1429760 1453824 1642752 1579776 1578752 1550848 1555712 1532928 1537024 1614336 1462528 1462272 1562624 1640192 1292800 1565440 1500928 1511680 1540096 408576 1432320 1626112 1643776 1509120 1095168 1637120 1487872 1643520 453120 1477120 1540352 1445120 1547008 1428480...
result:
wrong answer 1st numbers differ - expected: '3240', found: '829440'
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?...