题目描述
下标从 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。