题目背景

出题	标程	数据	验题	题解
Pekemetier			cq_zry & lOlAKME	Pekemetier

题目描述

给定一个仅包含 0、1 和 ? 的字符串，你需要将字符串中的每个 ? 分别替换成 0 或 1 之一。也就是说替换成一个 $01$ 字符串。求有多少种替换方案，使得替换后的字符串满足：恰好拥有奇数个不同的子序列（包含空串）的非空子串的个数为奇数。特别地，如果字符串中不包含 ?，应将其自身视为唯一的替换方案。

每个数据点会给定一个字符串 $s$ ，然后每次对 $s$ 的一个子串进行询问，答案对 $998244353$ 取模。

输入格式

第一行一个整数 $n$。

第二行一个长为 $n$ 的字符串 $s$，仅包含 0、1 和 ?。

第三行一个整数 $m$ 表示询问次数。

接下来 $m$ 行，每行两个整数 $l,r$ 表示对子串 $s_{l,r}$ 进行一次询问。

输出格式

输出 $m$ 行，每行一个整数表示答案，对 $998244353$ 取模。

不存在合法方案则输出 0。

5
100?1
5
1 5
1 4
2 5
3 4
1 3

1
0
1
1
1

20
1110??01001010?1?110
20
1 20
5 16
11 16
10 13
5 14
13 17
1 18
1 7
6 9
15 19
12 17
17 18
4 11
3 13
13 15
18 19
2 8
7 13
4 15
9 18

3
2
2
0
4
2
13
3
0
1
3
1
2
2
2
1
2
1
1
3

提示

【样例解释】

对于【样例#1】的第一个询问 1 5，有 $2$ 种替换方案，分别为字符串 10001 和 10011。

其中 10001 有 $3$ 个子串满足不同的子序列的个数为奇数：10001，拥有 $15$ 个不同的子序列；$s'_ {2,3}$ 和 $s'_ {3,4}$ 均为 00，都拥有 $3$ 个不同的子序列。

而 10011 则拥有 $4$ 个子串满足不同的子序列的个数为奇数，分别为 1001、00、0011、11。

10001 有奇数个子串满足子序列个数为奇数，因此计入答案；而 10011 有偶数个，因此不计入答案。

对于【样例#2】的第一个询问 1 20，$s_{1,20}$ 有 $4$ 个 ?，因此有 $2^4=16$ 种替换方案。

---

【数据范围】

本题采用捆绑测试。

$\text{Subtask}$	$n\leq$	$m\leq$	特殊性质	$\text{Score}$
$1$	$10$			$10$
$2$	$100$		$s$ 不包含 ?
$3$	$500$			$20$
$4$	$1000$
$5$	$5000$	$5000$		$10$
$6$		$10^5$
$7$	$5\times10^4$	$3\times 10^5$		$20$

对于 $100\%$ 的数据，满足 $1\leq n\leq 5\times10^4$，$1\leq m\leq 3\times10^5$，$s$ 仅包含 0、1 和 ?。

---

【提示与说明】

子串：在原来的字符串中选出一段连续字符组成的字符串。一个长为 $n$ 的字符串有 $\frac{n(n+1)}{2}$ 个子串。例如字符串 121 共有 $6$ 个子串，分别为 1、2、1、12、21、121。注意在本题中，空串不算一个子串。

子序列：在原来的字符串中任意删去若干个字符（也可以不删）形成的的字符串。例如字符串 0110 拥有 $11$ 个不同的子序列，分别为空串、0、1、00、01、10、11、010、011、110、0110。注意在本题中，空串也算一个子序列。