#PQJ1808x9464. QOJ 1808_9464

    ID: 2707 传统题 4000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2024-2025 集训队互测字符串

QOJ 1808_9464

标题: 基础 01? 练习题 - Problem - QOJ.ac

#9464. 基础 01? 练习题

Statistics

The problem was used in the following contests:

题目描述

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

  • P0=0;
  • P2n=Pn;
  • P2n+1=1−Pn。

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

01101001100101101001011001101001⋯

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

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

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

g(S)=∑0≤l≤r<|S|f(SlSl+1⋯Sr)

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

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

由于答案可能很大,所以输出答案对 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,m≤15 和特殊性质 C。

样例 3

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

样例 4

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

样例 5

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

数据范围

对于 100% 的数据,1≤n≤5×104,1≤m≤2×105,0≤l≤r<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

  • 特殊性质 A:r−l+1≤15;
  • 特殊性质 B:S 中 ? 的个数不超过 8;
  • 特殊性质 C:l=0。