← 返回题目列表

Codeforces · 2187/D

D. 很酷的问题

中文机器翻译题面 查看原题

有两个整数常量 $$$x$$$ 和 $$$y$$$。

对于长度为 $$$n$$$ 的二进制 $$$^{\text{∗}}$$$ 字符串 $$$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$$$。

给你一个不完整的二进制字符串$$$s$$$,长度为$$$n$$$,其中缺少一些字符,用$$$\mathtt{?}$$$表示。整数 $$$k$$$ 被称为 酷 当且仅当存在一种方法将 $$$s$$$ 中的每个 $$$\mathtt{?}$$$ 替换为 $$$\mathtt{0}$$$ 或 $$$\mathtt{1}$$$,使得 $$$f(s)=k$$$。

你的任务是计算所有的总和 酷 整数,以 $$$998\,244\,353$$$ 为模。

$$$^{\text{*}}$$$二进制字符串是每个字符为 $$$\mathtt{0}$$$ 或 $$$\mathtt{1}$$$ 的字符串。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。

输出

对于每个测试用例,输出一个整数 - 所有测试用例的总和 酷 以 $$$998\,244\,353$$$ 为模的整数。

示例

输入
复制

4
1 1 2
0
1 1 2
?
3 7 5
?0?
7 114514 191981
?1?????

输出
复制

1
3
100
8039591

注意

在第一个测试用例中,字符串 $$$s$$$ 已经确定,并且它的 生成数组 是 $$$[0, 1]$$$。因此,$$$f(s)=1$$$,并且唯一 酷 整数是$$$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$$$

因此,所有的总和 酷 整数是$$$42+12+36+10=100$$$。