「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`。注意在本题中,空串也算一个子序列。