P8885 "JEOI-R1" Subsequences

| Problem Setter | Reference Solution | testdata | Validator | Editorial | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | [Pekemetier](/user/146070) | [Pekemetier](/user/146070) | [Pekemetier](/user/146070) | [cq_zry](https://www.luogu.com.cn/user/734533) & [lOlAKME](/user/768786) | [Pekemetier](/user/146070) |

You are given a string that contains only `0`, `1`, and `?`. You need to replace each `?` with either `0` or `1`. That is, turn it into a $01$ string. Count how many replacement schemes make the resulting string satisfy the following condition: Among all non-empty substrings, the number of substrings that have an odd number of **distinct** subsequences (including the empty string) is odd. In particular, if the string does not contain `?`, then the string itself should be treated as the only replacement scheme. Each test gives a string $s$, and then asks queries on substrings of $s$. Output each answer modulo $998244353$.

The first line contains an integer $n$. The second line contains a string $s$ of length $n$, consisting only of `0`, `1`, and `?`. The third line contains an integer $m$, the number of queries. The next $m$ lines each contain two integers $l, r$, meaning a query on the substring $s_{l,r}$.

Output $m$ lines, each containing one integer: the answer modulo $998244353$. If there is no valid scheme, output `0`.

**Sample Explanation** For the first query `1 5` in Sample \#1, there are $2$ replacement schemes: the strings `10001` and `10011`. For `10001`, there are $3$ substrings whose number of distinct subsequences is odd: `10001`, which has $15$ distinct subsequences; and $s'_{2,3}$ and $s'_{3,4}`, both equal to `00`, each having $3$ distinct subsequences. For `10011`, there are $4$ substrings whose number of distinct subsequences is odd: `1001`, `00`, `0011`, and `11`. `10001` has an odd number of such substrings, so it is counted in the answer; `10011` has an even number, so it is not counted. For the first query `1 20` in Sample \#2, $s_{1,20}$ has $4$ `?`, so there are $2^4 = 16$ replacement schemes. --- **Constraints** **This problem uses bundled subtasks.** | $\text{Subtask}$ | $n\leq$ | $m\leq$ | Special Property | $\text{Score}$ | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | $10$ | | $10$ | | $2$ | $100$ | $100$ | $s$ contains no `?` | $10$ | | $3$ | $500$ | $500$ | $s$ contains no `?` | $20$ | | $4$ | $1000$ | $1000$ | | $20$ | | $5$ | $5000$ | $5000$ | | $10$ | | $6$ | $5000$ | $10^5$ | | $10$ | | $7$ | $5\times10^4$ | $3\times 10^5$ | | $20$ | For $100\%$ of the testdata, $1\leq n\leq 5\times10^4$, $1\leq m\leq 3\times10^5$, and $s$ contains only `0`, `1`, and `?`. --- **Notes and Explanation** Substring: a string formed by choosing a continuous segment from the original string. A string of length $n$ has $\frac{n(n+1)}{2}$ substrings. For example, the string `121` has $6$ substrings: `1`, `2`, `1`, `12`, `21`, `121`. Note that in this problem, the empty string is not a substring. Subsequence: a string formed by deleting any number of characters from the original string (possibly deleting none). For example, the string `0110` has $11$ distinct subsequences: the empty string, `0`, `1`, `00`, `01`, `10`, `11`, `010`, `011`, `110`, `0110`. Note that in this problem, the empty string is also considered a subsequence. Translated by ChatGPT 5