P12465 『FCRT / 1 - 2』Parity

CuteChat 发现自己乘坐的是 $\color{#d20000}01\color{black}010$ 号车，他来到了 $1$ 号车厢，因此看到了 $\color{#d20000}{010101}$ 的车厢号。车厢号中有奇数个 $1$，而对应的列车号中有偶数个 $1$。

定义函数 $\operatorname{Pari}(x)$，表示非负整数 $x$ 的二进制表示中 $1$ 的个数模 $2$ 的结果。例如，$\operatorname{Pari}(5) = 2 \bmod 2 = 0$。 给定一个长度为 $n$ 的二进制字符串 $S$，定义 $\text{Sub}(l, r)$ 表示 $S$ 的第 $l$ 到第 $r$ 个字符组成的二进制数转换成十进制数的值。 你需要处理 $q$ 次询问，每次询问给定两个参数 $l, r$，求解 $\displaystyle\sum_{x=0}^{\operatorname{Sub}(l, r)}\operatorname{Pari}(x)$，结果对 $998244353$ 取模。 注意字符串下标从 $1$ 开始。

无

无

#### 【样例 1 解释】 - 对于 $x = 1$，二进制为 $1$，$\text{Pari}(1) = 1$。 - 对于 $x = 2$，二进制为 $10$，$\text{Pari}(2) = 1$。 - 对于 $x = 4$，二进制为 $100$，$\text{Pari}(4) = 1$。 - 对于 $x = 7$，二进制为 $111$，$\text{Pari}(7) = 1$。 - 对于 $x = 8$，二进制为 $1000$，$\text{Pari}(8) = 1$。 因此，在 $0\sim10$ 的范围内，$\operatorname{Pari}$ 函数值为 $1$ 的有 $1, 2, 4, 7, 8$，这些数字的二进制表示中有奇数个 $1$。 - 对于第一次询问，$\operatorname{Sub}(3,6)=5$，故答案为 $3$。 - 对于第二次询问，$\operatorname{Sub}(2,5)=10$，故答案为 $5$。 - 对于第三次询问，$\operatorname{Sub}(1,2)=1$，故答案为 $1$。 - 对于第四次询问，$\operatorname{Sub}(5,5)=0$，故答案为 $0$。 #### 【数据范围】 **本题采用捆绑测试。** 对于所有测试数据，保证 $1\le n,q \le 2\times10^{5}$，$1\le l\le r\le n$，$S_i\in\{0,1\}$。所有输入数据均为非负整数或 $01$ 字符串。 - Subtask 1（15 Points）：$n,q\le20$。 - Subtask 2（10 Points）：$n\le20$。 - Subtask 3（15 Points）：$S$ 的所有字符都是 $1$。 - Subtask 4（10 Points）：$n,q\le10^3$，$S_r=1$。 - Subtask 5（15 Points）：$n,q\le10^3$。 - Subtask 6（15 Points）：$S_r=1$。 - Subtask 7（20 Points）：无特殊限制。