QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#706416	#9464. 基础 01? 练习题	Aaronwrq^#	20	2490ms	331108kb	C++14	2.3kb	2024-11-03 11:12:48	2024-11-03 11:12:48

Judging History

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

[2024-11-03 11:12:48]
评测

测评结果：20
用时：2490ms
内存：331108kb

查看

[2024-11-03 11:12:48]
提交

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] = 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;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10

Accepted

Test #1:

score: 10

Accepted

time: 1ms

memory: 3976kb

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:

result:

ok 15 numbers

Test #2:

score: 10

Accepted

time: 1ms

memory: 3564kb

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:

result:

ok 15 numbers

Test #3:

score: 10

Accepted

time: 1ms

memory: 3684kb

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:

result:

ok 15 numbers

Test #4:

score: 10

Accepted

time: 2ms

memory: 3628kb

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:

result:

ok 15 numbers

Test #5:

score: 10

Accepted

time: 1ms

memory: 3972kb

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:

result:

ok 15 numbers

Test #6:

score: 10

Accepted

time: 1ms

memory: 3624kb

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:

result:

ok 15 numbers

Subtask #2:

score: 0

Wrong Answer

Test #7:

score: 0

Wrong Answer

time: 43ms

memory: 3768kb

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:

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: 386ms

memory: 82668kb

input:

500 1000
011000100010010010010010110010101100101100101011010010011001101001011010011000010011010001011010000001100101100110100101101001001011010010110010110100101100111001100111010011010010110100110010110100101100110101000101100110100110010110100101100110100101101?01101101100101011001010010100110010...

output:

result:

ok 1000 numbers

Test #32:

score: 5

Accepted

time: 374ms

memory: 82624kb

input:

500 1000
0010100100010011011101100101000010010110100101101001010010110101001?1001?0100100010010100010110110010111101110110001010010001011001010001010001001100101010011010110100110101111001001010101101000101100101100111011110110100100011010?101110010101111000101010000001110011010011000101100100101100...

output:

result:

ok 1000 numbers

Test #33:

score: 5

Accepted

time: 357ms

memory: 82628kb

input:

500 1000
101001001?11011010010111100110010110101010010001111?10101010001101011011001110100101110011010011101011101110110100101011000001000110110000101000010010011?0100100100010001010001010011010011010001?011010011001110110101101011110100011100100101110011011010110101101010110100001101001110000101101...

output:

result:

ok 1000 numbers

Test #34:

score: 5

Accepted

time: 366ms

memory: 84636kb

input:

500 1000
11010011001101101001011010110010100110110110?01001110101001010100111?010110011001001001101001110100101001100101101001001001101101001111100110100110010110011101100000100110111010001010011001101001011?1110011011101010010111001101101101101001010010001001011011001?010011001011110010?1100101?011...

output:

result:

ok 1000 numbers

Test #35:

score: 5

Accepted

time: 390ms

memory: 82672kb

input:

500 1000
01100011001011011100101100110100110010110100010011010110011010010010110100100110010011001011001101001011001101001?110100101100011010011001011001101001011011?01001011010000101100110100101101100110101100110100101101001100101100110010110011011000011011001011000011010010110100101100111001011001...

output:

result:

ok 1000 numbers

Test #36:

score: 5

Accepted

time: 392ms

memory: 82632kb

input:

500 1000
0110100110010110100101?00110100101101001100101100101101001100101100110100110010110101001011001101010100?100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001100?0110011010110100110010110011010010110?001100101100110?001100101...

output:

result:

ok 1000 numbers

Subtask #7:

score: 5

Accepted

Test #37:

score: 5

Accepted

time: 2490ms

memory: 330932kb

input:

1000 2000
01100101101001011001101001011010011001011010010110011010011001011001101001011010011001011010010110011010000110100101101001100101100110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100101101001100101101001011001101001...

output:

result:

ok 2000 numbers

Test #38:

score: 5

Accepted

time: 2375ms

memory: 330844kb

input:

1000 2000
010000101101000010011011001?111011010010101100110010110010010110011001011011110010111001011011001001110100101100110100000100110100100110110010101100110100110101100110100110010110010101101001100010011010101011010010100110?001001101110010110100100101011010011101001111110100110011010101011001...

output:

result:

ok 2000 numbers

Test #39:

score: 5

Accepted

time: 2399ms

memory: 330872kb

input:

1000 2000
0110100011010011001011100?01111010011001011001001011010100011001100100?011000011001011001101001011010011011001011100101100110100101101001100101100110100110010110100101110100110100110100110010011001011010001010100110010110011001100101101001010110100101010101001100101100101001011001101001100...

output:

result:

ok 2000 numbers

Test #40:

score: 5

Accepted

time: 2431ms

memory: 330992kb

input:

1000 2000
01100110100110010110100101100110100101101001100001011010010110011010010110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110011010010110100110010110011010011001011010010110011010011001011001100101101001101001011010011001011010010110011010...

output:

result:

ok 2000 numbers

Test #41:

score: 5

Accepted

time: 2418ms

memory: 331108kb

input:

1000 2000
1101001100101001100101100110100101101001101100110100110010110011010010110100110010110100101100110100110010110100101101010011001011010001011001101001011010011001011010010011010010110011010010110010110100110010100110010110100101100110100110010110011010011?010110011010010110100110010110011010...

output:

result:

ok 2000 numbers

Test #42:

score: 5

Accepted

time: 2406ms

memory: 330936kb

input:

1000 2000
00101101001011001101001011010011001011010?1011001101001100?01100110100101101001100101101?0101100110100101101001101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100010110100101100110100?1001011001101001011010011001011010010110011010010...

output:

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?...