QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #706390 | #9464. 基础 01? 练习题 | Aaronwrq# | 0 | 2352ms | 330876kb | C++14 | 2.3kb | 2024-11-03 11:01:45 | 2024-11-03 11:01:46 |
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, 13131}, 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] = 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];
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: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3748kb
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:
499134031 1564 748683319 27753 27753 7440 748685016 436731909 546 249563179 6352 2 32114 6352 249561112
result:
wrong answer 1st numbers differ - expected: '25883', found: '499134031'
Subtask #2:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 39ms
memory: 3880kb
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:
575859 748741336 75762 311984420 686294540 75762 3388 73780 873463818 623914200 717488195 31195588 2 73780 873464979 1391 418209985 343147568 640619 600506564 518 135702 623938544 1 52 623922713 75762 301 151825 575859 249564517 374429853 8038 151825 858841169 16745 31815 623922713 809123873 7486884...
result:
wrong answer 1st numbers differ - expected: '1336712', found: '575859'
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: 351ms
memory: 82704kb
input:
500 1000 011000100010010010010010110010101100101100101011010010011001101001011010011000010011010001011010000001100101100110100101101001001011010010110010110100101100111001100111010011010010110100110010110100101100110101000101100110100110010110100101100110100101101?01101101100101011001010010100110010...
output:
36 130 149 112 234 1864 1184 1680 330 872 560 1352 152 1864 1896 374 1900 94 1016 1876 168 1164 34 91 780 151 40 1308 1176 316 1612 118 1472 1860 1696 1784 1504 1960 2 1292 1516 58 656 1192 1540 54 162 988 2036 1584 1632 1572 332 386 1564 184 344 121 198 149 1588 50 1928 804 1336 612 1168 1700 1700 ...
result:
wrong answer 1st numbers differ - expected: '399', found: '36'
Subtask #7:
score: 0
Wrong Answer
Test #37:
score: 0
Wrong Answer
time: 2352ms
memory: 330876kb
input:
1000 2000 01100101101001011001101001011010011001011010010110011010011001011001101001011010011001011010010110011010000110100101101001100101100110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100101101001100101101001011001101001...
output:
3240 100416 99824 1651968 5585 5679 1642752 98736 98672 48464 48616 23952 24016 100896 5713 5712 97664 1640192 5050 97840 23452 23620 24064 1596 5595 813056 1643776 23580 4278 1637120 11624 1643520 1770 11540 24068 5645 24172 5580 1891 5748 5734 24136 23492 11638 23700 812288 98896 23844 811008 325 ...
result:
wrong answer 2nd numbers differ - expected: '660160', found: '100416'
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?...