「JEOI-R1」子序列

题目背景

| 出题 | 标程 | 数据 | 验题 | 题解 | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | [Pekemetier](/user/146070) | [Pekemetier](/user/146070) | [Pekemetier](/user/146070) | [cq_zry](https://www.luogu.com.cn/user/734533) & [lOlAKME](/user/768786) | [Pekemetier](/user/146070) |

题目描述

给定一个仅包含 `0`、`1` 和 `?` 的字符串,你需要将字符串中的每个 `?` 分别替换成 `0` 或 `1` 之一。也就是说替换成一个 $01$ 字符串。求有多少种替换方案,使得替换后的字符串满足:恰好拥有奇数个**不同的**子序列(包含空串)的非空子串的个数为奇数。特别地,如果字符串中不包含 `?`,应将其自身视为唯一的替换方案。 每个数据点会给定一个字符串 $s$ ,然后每次对 $s$ 的一个子串进行询问,答案对 $998244353$ 取模。

输入输出格式

输入格式


第一行一个整数 $n$。 第二行一个长为 $n$ 的字符串 $s$,仅包含 `0`、`1` 和 `?`。 第三行一个整数 $m$ 表示询问次数。 接下来 $m$ 行,每行两个整数 $l,r$ 表示对子串 $s_{l,r}$ 进行一次询问。

输出格式


输出 $m$ 行,每行一个整数表示答案,对 $998244353$ 取模。 不存在合法方案则输出 `0`。

输入输出样例

输入样例 #1

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

输出样例 #1

1
0
1
1
1

输入样例 #2

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

输出样例 #2

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$ | | $10$ | | $2$ | $100$ | $100$ | $s$ 不包含 `?` | $10$ | | $3$ | $500$ | $500$ | $s$ 不包含 `?` | $20$ | | $4$ | $1000$ | $1000$ | | $20$ | | $5$ | $5000$ | $5000$ | | $10$ | | $6$ | $5000$ | $10^5$ | | $10$ | | $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`。注意在本题中,空串也算一个子序列。