P12473 [集训队互测 2024] 基础 01? 练习题

下标从 $0$ 开始的 $\texttt{01}$ 无穷序列 $P$ 由如下方式生成： - $P_0=\texttt{0}$； - $P_{2n}=P_{n}$； - $P_{2n+1}=\texttt{1}-P_{n}$。 这里给出 $P$ 序列的前若干项： $$ \texttt{01101001100101101001011001101001}\cdots $$ 方便起见，接下来将 $P$ 看做一个字符串，且字符串的下标均从 $0$ 开始。 定义 $f(S)$ 表示有限 $\texttt{01}$ 串 $S$ 是否为 $P$ 的子串，若是，则 $f(S)=1$，否则为 $0$。 定义 $g(S)$ 表示有限 $\texttt{01}$ 串 $S$ 中【是 $P$ 的子串】的子串个数，即： $$ g(S)=\sum_{0\le l \le r < |S|}f(S_lS_{l+1}\cdots S_r) $$ 接下来定义 $h(S)$：对于一个仅包含 $\texttt{0,1,?}$ 的有限字符串 $S$ 中，将 $S$ 中 $\texttt{?}$ 各自替换成 $\texttt{0}$ 或 $\texttt{1}$，则 $h(S)$ 表示所有可能生成的 $\texttt{01}$ 串 $T$ 的 $g(T)$ 之和。 给定长度为 $n$ 的仅包含 $\texttt{0,1,?}$ 的字符串 $S$，有 $m$ 次询问，每次询问给出 $l,r$，求出 $h(S_lS_{l+1}\cdots S_r)$ 的值。 由于答案可能很大，所以输出答案对 $998244353$ 取模的结果。

第一行两个正整数 $n,m$。 第二行一个长度为 $n$ 的仅包含 $\texttt{0,1,?}$ 的字符串 $S$。 接下来 $m$ 行，每行两个非负整数 $l,r$，表示一组询问。

输出 $m$ 行，对于每组询问输出一行一个整数表示答案。

### 样例 2 见下发文件，满足 $n,m \le 15$ 和特殊性质 C。 ### 样例 3 见下发文件，满足 $n,m \le 100$ 和特殊性质 B。 ### 样例 4 见下发文件，满足 $n,m \le 10^3$ 和特殊性质 BC。 ### 样例 5 见下发文件，满足 $n,m \le 10^3$ 和特殊性质 A。 ## 数据范围 对于 $100\%$ 的数据，$1\le n \le 5\times 10^4$，$1\le m \le 2\times 10^5$，$0\le l_1\le r_1 < n$，$0\le l_2\le r_2 < n$。 | 子任务 | $n\le$ | $m\le$ | 特殊性质 | 分值 | | ----------- | -------------- | -------------- | -------- | ---- | | 1 | $15$ | $15$ | A | 10 | | 2 | $20$ | $2\times 10^5$ | 无 | 10 | | 3 | $5\times 10^4$ | $2\times 10^5$ | A | 5 | | 4 | $5\times 10^4$ | $1$ | BC | 5 | | 5 | $5\times 10^4$ | $1$ | C | 15 | | 6 | $500$ | $10^3$ | B | 5 | | 7 | $10^3$ | $2\times 10^3$ | BC | 5 | | 8 | $5\times 10^3$ | $10^5$ | C | 10 | | 9 | $2\times 10^4$ | $10^5$ | 无 | 15 | | 10 | $5\times 10^4$ | $2\times 10^5$ | 无 | 20 | 特殊性质 A：$r-l+1 \le 15$； 特殊性质 B：$S$ 中 $\texttt{?}$ 的个数不超过 $8$； 特殊性质 C：$l=0$。