CF2187D Cool Problem

有两个整数常数 $x$ 和 $y$。 对于一个长度为 $n$ 的二进制字符串 $r$，我们定义它的生成数组为 $c=[c_0,c_1,\ldots,c_n]$，其中 $c_0=0$，并且对每个 $1 \le i \le n$： - 如果 $r_i=\mathtt{0}$，那么 $c_i=x+c_{i-1}$； - 如果 $r_i=\mathtt{1}$，那么 $c_i=y-c_{i-1}$。 此外，我们定义 $f(r)=\sum\limits_{i=1}^n c_i$。 现在给定一个长度为 $n$ 的不完整二进制字符串 $s$，其中有些字符缺失，用 $\mathtt{?}$ 表示。若存在一种方式将 $s$ 中的每个 $\mathtt{?}$ 替换成 $\mathtt{0}$ 或 $\mathtt{1}$，使得 $f(s)=k$，那么整数 $k$ 被称为“cool”整数。 你的任务是计算所有 cool 整数的和，结果对 $998\,244\,353$ 取模。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。每个测试用例的描述如下。 每个测试用例的第一行包含三个整数 $n$、$x$ 和 $y$（$1 \le n \le 10^5$，$1 \le x,y \le 10^6$），分别表示字符串 $s$ 的长度和两个给定的常数。 第二行包含长度为 $n$ 的不完整二进制字符串 $s$（$s_i \in \{\mathtt{0},\mathtt{1},\mathtt{?}\}$）。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出一个整数，表示所有 cool 整数之和，对 $998\,244\,353$ 取模。

在第一个测试用例中，字符串 $s$ 已经确定，其生成数组为 $[0, 1]$。因此 $f(s)=1$，唯一的 cool 整数为 $1$。 在第三个测试用例中，有四种方式补全字符串 $s$： | $s$ | 生成数组 | $f(s)$ | |---------|---------------------|--------| | $\mathtt{000}$ | $[0, 7, 14, 21]$ | $42$ | | $\mathtt{001}$ | $[0, 7, 14, -9]$ | $12$ | | $\mathtt{100}$ | $[0, 5, 12, 19]$ | $36$ | | $\mathtt{101}$ | $[0, 5, 12, -7]$ | $10$ | 因此，所有 cool 整数之和为 $42+12+36+10=100$。 由 ChatGPT 5 翻译