← 返回题目列表

Codeforces · 1984/F

F. 重建

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

有一个隐藏数组 $$$a_1, a_2, \ldots, a_n$$$,长度为 $$$n$$$,其元素是 $$$-m$$$ 和 $$$m$$$(含)之间的整数。

给定一个长度为 $$$n$$$ 的数组 $$$b_1, b_2, \ldots, b_n$$$ 和一个长度为 $$$n$$$ 的字符串 $$$s$$$,其中包含字符 $$$\texttt{P}$$$、$$$\texttt{S}$$$ 和 $$$\texttt{?}$$$。

对于从 $$$1$$$ 到 $$$n$$$(含)的每个 $$$i$$$,我们必须:

- 如果 $$$s_i = \texttt{P}$$$,$$$b_i$$$ 是 $$$a_1$$$ 到 $$$a_i$$$ 的总和。
- 如果 $$$s_i = \texttt{S}$$$,$$$b_i$$$ 是 $$$a_i$$$ 到 $$$a_n$$$ 的总和。

输出将 $$$s$$$ 中的所有 $$$\texttt{?}$$$ 替换为 $$$\texttt{P}$$$ 或 $$$\texttt{S}$$$ 的方法数,使得存在一个数组 $$$a_1, a_2, \ldots, a_n$$$,其中元素的绝对值不超过 $$$m$$$ 满足下式给出的约束数组$$$b_1、b_2、\ldots、b_n$$$ 和字符串$$$s$$$。

由于答案可能很大,因此输出它对 $$$998\,244\,353$$$ 取模。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 2 \cdot 10^3$$$, $$$2 \leq m \leq 10^{9}$$$) - 隐藏数组 $$$a_1, a_2, \ldots, a_n$$$ 的长度和元素 $$$a_i$$$ 的最大绝对值。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$,由字符 $$$\texttt{P}$$$、$$$\texttt{S}$$$ 和 $$$\texttt{?}$$$ 组成。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$|b_i| \leq m \cdot n$$$)。

所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^3$$$。

输出

对于每个测试用例,输出一个整数 - 将 $$$s$$$ 中的所有 $$$\texttt{?}$$$ 替换为 $$$\texttt{P}$$$ 或 $$$\texttt{S}$$$ 的方法数量,从而导致存在有效数组 $$$a_1, a_2, \ldots, a_n$$$, 模$$$998\,244\,353$$$。

示例

输入 #1

6
4 10
PSPP
1 9 8 10
4 1000000000
????
1 1 1 4000000000
8 1000000000
?P?SSP?P
-857095623 -1424391899 -851974476 673437144 471253851 -543483033 364945701 -178537332
4 7
PPSS
4 2 1 3
9 20
?????????
1 2 3 4 5 6 7 8 9
3 1000000000
P??
-145463248 -974068460 -1287458396

输出 #1

1
0
2
1
14
1

注意

在第一个测试用例中,我们可以看到以下数组满足所有约束,因此答案是$$$1$$$:

1. $$$\texttt{P}$$$ — $$${[\color{red}{\textbf{1}},3,4,2]}$$$:$$$1$$$ 的总和。
2. $$$\texttt{S}$$$ — $$${[1,\color{red}{\textbf{3},4,2}]}$$$:$$$9$$$ 的总和。
3. $$$\texttt{P}$$$ — $$${[\color{red}{1,3,\textbf{4}},2]}$$$:$$$8$$$ 的总和。
4. $$$\texttt{P}$$$ — $$${[\color{red}{1,3,4,\textbf{2}}]}$$$:$$$10$$$ 的总和。

在第二个测试用例中,可以证明没有数组 $$$a$$$ 包含所有 $$$|a_i| \leq m = 10^9$$$ 满足所有约束。