别样的 Parity 大战 一天，仵沉蛋给我打来电话。他说：“你敢不敢和我举行 Parity 大战？”我豪爽地答应了：“我当然敢！周日下午在 xx 路 xx 大厦，给定长度为
n n n 的二进制字符串
S S S 和
q q q 次查询，每次查询对于
[ l , r ] [l,r] [ l , r ] ，要计算
∑ x = 0 Sub ( l , r ) Pari ( x ) m o d 998244353 \sum_{x=0}^{\operatorname{Sub}(l,r)}\operatorname{Pari}(x) \bmod 998244353 ∑ x = 0 Sub ( l , r ) Pari ( x ) mod 998244353 ，谁不来谁就是怂货。”
我原本以为我恐吓了仵沉蛋，仵沉蛋应该躲在家，不敢找我，便准备用
O ( N ) O(N) O ( N ) 暴力枚举计算：
CPP long long ans = 0 ;
for (int x = 0 ; x <= N; x++) {
ans += __builtin_popcount(x) % 2 ;
}
可正当这时，我听到了音乐声，一看，竟然是我的暴力枚举 TLE 了，仵沉蛋打来电话：“小废物，不会用
Pari \operatorname{Pari} Pari 函数的性质？再不会你的锣鼓账号就要被我机惨了！”我回击道：“我要用
S ( N ) = ∑ ( − 1 ) p o p c o u n t ( x ) S(N)=∑(-1)^{popcount(x)} S ( N ) = ∑ ( − 1 ) p o p co u n t ( x ) 的公式和预处理，把你 hack 掉，你说好不好啊。”
他吓得没再回应我，可是到了周日，仵沉蛋竟然又给我打电话了，他还真要和我举行 Parity 大战，于是我按照约定，到达了 xx 大厦，可他已经等我很久了。
第一回合，我占上风，利用公式
f ( N ) = ( N + 1 ) − S ( N ) 2 f(N)=\frac{(N+1)-S(N)}{2} f ( N ) = 2 ( N + 1 ) − S ( N ) 发起进攻：
CPP long long X = (Nv + 1 ) % mod;
long long ans = (X - Sv) * inv2 % mod;
仵沉蛋还在手算
Sub ( l , r ) \operatorname{Sub}(l,r) Sub ( l , r ) 的值，他比不过我，到了第六回合，他就主动认输了。
第二回合，他开始占上风，我也不甘势弱，我们僵持了一百多个回合，我轻敌地只预处理了前缀和：
CPP Fw[0 ] = s[0 ]-'0' ;
for (int i=1 ; i<n; i++) {
Fw[i] = (Fw[i-1 ]*2 + (s[i]-'0' )) % mod;
}
却忽略了全零子串的边界情况：
CPP if (nxt[l0] == -1 || nxt[l0] > r0) {
}
被他击败了。
从那时开始，我就不轻敌了，我认真研究他的套路，于是我总结出了一种方案：
预处理 n x t nxt n x t 1 1 1
CPP int last = -1 ;
for (int i=n-1 ; i>=0 ; i--){
if (s[i]=='1' ) last = i;
nxt[i] = last;
}
p o w 2 t pow2t p o w 2 t 存储
2 i m o d 998244353 2^i \bmod 998244353 2 i mod 998244353 **。
第二天，我们举行第三局，他使用祖传暴力算法，对我发动猛烈的攻击，我们势均力敌，平分秋色，
2 × 10 5 2\times 10^5 2 × 1 0 5 的查询使我们比了
3 3 3 个多小时，也没分出胜负。
后来，他不知不觉的睡着了，我趁着这个好机会，一记凌车漂移，一飞冲天，精准的预处理和
O ( 1 ) O(1) O ( 1 ) 查询：
CPP int pos = nxt[l0];
if (s[r0]=='1' ) Sv=0 ;
else {
int m = Cw[r0] - (pos?Cw[pos-1 ]:0 );
Sv = (m%2 )? -1 :1 ;
}
long long Nv = (Fw[r0] - Fw[pos-1 ]*pow2t[len]) % mod;
long long ans = ((Nv+1 - Sv) * inv2 % mod + mod) % mod;
打的他不敢还手，对他的打击比取模时忘记处理负模数还大：
CPP if (ans < 0 ) ans += mod;
下面是正常版题解 题意简述 题目要求计算对于给定的二进制字符串的子串所表示的数字
N N N ，求解：
∑ x = 0 N Pari ( x ) m o d 998244353 \sum_{x=0}^{N} \operatorname{Pari}(x) \bmod 998244353 ∑ x = 0 N Pari ( x ) mod 998244353 其中
Pari ( x ) \operatorname{Pari}(x) Pari ( x ) 是
x x x 的二进制表示中
1 1 1 的个数的奇偶性（即
1 1 1 的个数模
2 2 2 ）。
思路 我们可以将问题进行转化：定义函数
S ( N ) = ∑ x = 0 N ( − 1 ) popcount ( x ) S(N) = \sum_{x=0}^{N} (-1)^{\text{popcount}(x)} S ( N ) = ∑ x = 0 N ( − 1 ) popcount ( x ) ，则所求答案可表示为：
f ( N ) = ( N + 1 ) − S ( N ) 2 m o d 998244353 f(N) = \frac{(N + 1) - S(N)}{2} \bmod 998244353 f ( N ) = 2 ( N + 1 ) − S ( N ) mod 998244353 所以，我们只需思考如何求
S ( N ) S(N) S ( N ) 。考虑如下计算方式：
若
N = 0 N = 0 N = 0 ，则
S ( 0 ) = 1 S(0) = 1 S ( 0 ) = 1 。
对于
N > 0 N > 0 N > 0 ，设
a a a 是满足
2 a ≤ N 2^a \leq N 2 a ≤ N 的最大整数（即二进制表示的最高位
1 1 1 的位置），
b = N − 2 a b = N - 2^a b = N − 2 a 。则：
\begin{cases}
0 & \text{当 } a = 0 \text{ (即 } N=1\text{)} \\
-S(b) & \text{其他情况}
\end{cases}$$
- 设二进制子串去除前导零后为 $T$，则：
- 若 $T$ 为空（即 $N = 0$），$S(N) = 1$。
- 若 $T$ 的最后一个字符是 $1$，则 $S(N) = 0$。
- 否则，设 $m$ 为 $T$ 中 $1$ 的个数，则 $S(N) = (-1)^m$。
然后，为了提升算法效率，考虑如下优化：
- **预处理**：
- `nxt[i]`：从位置 $i$ 开始向右的第一个 $1$ 的位置（用于快速定位子串中第一个 $1$）。
- `Fw[i]`：前缀子串 $s[0..i]$ 表示的二进制数的值（取模后）。
- `Cw[i]`：前缀子串 $s[0..i]$ 中 $1$ 的个数。
- `pow2t[i]`：预处理 $2^i$ 取模后的值。
- **查询**：
1. 定位子串中第一个 $1$ 的位置 $pos$。
2. 若不存在 $1$，则 $N = 0$，直接 `return 0`。
3. 否则，根据子串 $s[pos..r]$ 的最后一个字符和其中 $1$ 的个数计算 $S(N)$。
4. 计算子串表示的二进制数 $N$（利用前缀和与快速幂）。
5. 最后，代入公式计算答案即可。
### Code
```cpp
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 200000; // 最大字符串长度
const int mod = 998244353; // 模数
const long long inv2 = (mod + 1) / 2; // 2的逆元，用于除法
int n, q; // 字符串长度和查询数
char s[MAXN + 10]; // 存储输入的二进制字符串（下标0开始）
int nxt[MAXN + 10]; // nxt[i]: 从位置i开始向右的第一个'1'的位置，没有则为-1
long long Fw[MAXN + 10]; // Fw[i]: 前缀子串s[0..i]的二进制值取 mod
int Cw[MAXN + 10]; // Cw[i]: 前缀子串s[0..i]中'1'的个数
long long pow2t[MAXN + 10]; // pow2t[i]: 2^i 取 mod
int main() {
cin >> n >> q;
cin >> s;
// 预处理幂表：计算2^i mod mod (0 <= i <= MAXN)
pow2t[0] = 1;
for (int i = 1; i <= MAXN; i++) {
pow2t[i] = (pow2t[i - 1] * 2) % mod;
}
// 预处理nxt：从右向左扫描，记录每个位置开始向右的第一个'1'
int last = -1; // 记录最近遇到的'1'的位置
for (int i = n - 1; i >= 0; i--) {
if (s[i] == '1') {
last = i; // 更新最近'1'的位置
}
nxt[i] = last; // 记录当前位置开始的第一个'1'
}
// 预处理前缀和数组Fw和Cw
if (n > 0) {
// 初始化第一个字符
Fw[0] = s[0] - '0'; // 数值
Cw[0] = (s[0] == '1') ? 1 : 0; // '1'的个数
// 计算后续位置
for (int i = 1; i < n; i++) {
// Fw[i] = 前i-1位的值左移1位 + 当前位的值
Fw[i] = (Fw[i - 1] * 2 + (s[i] - '0')) % mod;
// Cw[i] = 前i-1位的'1'个数 + 当前位是否为'1'
Cw[i] = Cw[i - 1] + ((s[i] == '1') ? 1 : 0);
}
}
// 处理每个查询
while (q--) {
int l, r;
cin >> l >> r;
// 转换为0-indexed下标
int l0 = l - 1;
int r0 = r - 1;
// 情况1：子串中没有'1'（全0）
if (nxt[l0] == -1 || nxt[l0] > r0) {
// N = 0, S(0)=1
long long X = 1; // X = N + 1 = 1
long long Sv = 1; // S(0)=1
// f(N) = (X - Sv) / 2
long long ans = (X - Sv) % mod;
if (ans < 0) ans += mod; // 处理负数（仵沉蛋就是这一步忘记了！）
ans = ans * inv2 % mod; // 乘以逆元
cout << ans << endl;
}
// 情况2：子串中有'1'
else {
int pos = nxt[l0]; // 第一个'1'的位置（0-indexed）
long long Sv; // 存储S(N)的值
// 判断子串最后一个字符（决定N的奇偶性）
if (s[r0] == '1') {
// N为奇数，S(N)=0
Sv = 0;
} else {
// N为偶数，计算有效子串中'1'的个数m
int m;
if (pos == 0) {
// 有效子串从0开始，直接取前缀
m = Cw[r0];
} else {
// 有效子串从pos开始，计算Cw[r0] - Cw[pos-1]
m = Cw[r0] - Cw[pos - 1];
}
// S(N) = (-1)^m
if (m % 2 == 0) {
Sv = 1;
} else {
Sv = -1;
}
}
// 计算有效子串表示的数值N
long long Nv;
int len = r0 - pos + 1; // 有效子串长度
if (pos == 0) {
// 有效子串从0开始，直接取前缀值
Nv = Fw[r0];
} else {
// 计算：子串值 = 整个前缀值 - 前pos-1部分左移len位的值
Nv = (Fw[r0] - Fw[pos - 1] * pow2t[len]) % mod;
if (Nv < 0) Nv += mod; // 处理负数（仵沉蛋就是这一步忘记了！）
}
// 计算答案 f(N) = ((N+1) - S(N)) / 2
long long X = (Nv + 1) % mod; // X = N+1
long long temp = (X - Sv) % mod; // temp = (N+1) - S(N)
if (temp < 0) temp += mod; // 处理负数（仵沉蛋就是这一步忘记了！）
long long ans = temp * inv2 % mod; // 乘以逆元
cout << ans << endl;
}
}
return 0;
}
```
其中查询时间复杂度为 $O(1)$，总时间复杂度 $O(n + q)$。