QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 512 MB Total points: 100

# 9464. 基础 01? 练习题

统计

题目描述

下标从 $0$ 开始的 $\texttt{01}$ 无穷序列 $P$ 由如下方式生成:

  • $P_0=0$;
  • $P_{2n}=P_{n}$;
  • $P_{2n+1}=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},\texttt{1},\texttt{?}$ 的有限字符串 $S$,将 $S$ 中 $\texttt{?}$ 各自替换成 $\texttt{0}$ 或 $\texttt{1}$,则 $h(S)$ 表示所有可能生成的 $\texttt{01}$ 串 $T$ 的 $g(T)$ 之和。

给定长度为 $n$ 的仅包含 $\texttt{0},\texttt{1},\texttt{?}$ 的字符串 $S$,有 $m$ 次询问,每次询问给出 $l,r$,求出 $h(S_lS_{l+1}\cdots S_r)$ 的值。

由于答案可能很大,所以输出答案对 $998244353$ 取模的结果。

输入格式

第一行两个正整数 $n,m$。

第二行一个长度为 $n$ 的仅包含 $\texttt{0},\texttt{1},\texttt{?}$ 的字符串 $S$。

接下来 $m$ 行,每行两个非负整数 $l,r$,表示一组询问。

输出格式

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

样例

样例输入 1

4 4
??00
0 0
0 1
0 2
0 3

样例输出 1

2
12
23
35

样例 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 \le r < n$。

子任务 $n \le$ $m \le$ 特殊性质 分值
1 15 15 A 10
2 20 $2 \times 10^5$ 10
3 $5 \times 10^4$ A 5
4 1 BC 5
5 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$ 15
10 $5 \times 10^4$ $2 \times 10^5$ 20
  • 特殊性质 A:$r-l+1 \le 15$;
  • 特殊性质 B:$S$ 中 $\texttt{?}$ 的个数不超过 8;
  • 特殊性质 C:$l=0$。