QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 512 MB Total points: 100
[+30]
统计

题目描述

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

  • P0=0
  • P2n=Pn
  • P2n+1=1Pn

这里给出 P 序列的前若干项:

01101001100101101001011001101001

方便起见,接下来将 P 看做一个字符串,且字符串的下标均从 0 开始。

定义 f(S) 表示有限 01S 是否为 P 的子串,若是,则 f(S)=1,否则为 0

定义 g(S) 表示有限 01S 中【是 P 的子串】的子串个数,即:

g(S)=0lr<|S|f(SlSl+1Sr)

接下来定义 h(S):对于一个仅包含 0,1,? 的有限字符串 S,将 S? 各自替换成 01,则 h(S) 表示所有可能生成的 01Tg(T) 之和。

给定长度为 n 的仅包含 0,1,? 的字符串 S,有 m 次询问,每次询问给出 l,r,求出 h(SlSl+1Sr) 的值。

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

输入格式

第一行两个正整数 n,m

第二行一个长度为 n 的仅包含 0,1,? 的字符串 S

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

输出格式

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

样例

样例输入 1

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

样例输出 1

2
12
23
35

样例 2

见下发文件,满足 n,m15 和特殊性质 C。

样例 3

见下发文件,满足 n,m100 和特殊性质 B。

样例 4

见下发文件,满足 n,m103 和特殊性质 BC。

样例 5

见下发文件,满足 n,m103 和特殊性质 A。

数据范围

对于 100% 的数据,1n5×1041m2×1050lr<n

子任务 n m 特殊性质 分值
1 15 15 A 10
2 20 2×105 10
3 5×104 A 5
4 1 BC 5
5 C 15
6 500 103 B 5
7 103 2×103 BC 5
8 5×103 105 C 10
9 2×104 15
10 5×104 2×105 20
  • 特殊性质 Arl+115
  • 特殊性质 BS? 的个数不超过 8;
  • 特殊性质 Cl=0