#1841. 基础 01? 练习题
基础 01? 练习题
基础 01? 练习题
题目描述
标题: 基础 01? 练习题 - Problem - QOJ.ac
#9464. 基础 01? 练习题
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。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4 4
??00
0 0
0 1
0 2
0 3
2
12
23
35
样例 2
15 15
?????1?1??11??1
0 14
0 3
0 1
0 5
0 13
0 0
0 0
0 9
0 14
0 10
0 0
0 6
0 5
0 5
0 11
53488
146
12
540
49226
2
2
8288
53488
9448
2
1346
540
540
10414