← 返回题目列表

Codeforces · 1442/B

B. 识别操作

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

我们从排列 $$$a_1, a_2, \ldots, a_n$$$ 和一个空数组 $$$b$$$ 开始。我们应用以下操作 $$$k$$$ 次。

在第 $$$i$$$ 次迭代中,我们选择索引 $$$t_i$$$ ($$$1 \le t_i \le n-i+1$$$),从数组中删除 $$$a_{t_i}$$$,并附加数字 $$$a_{t_i-1}$$$ 或 $$$a_{t_i+1}$$$ 之一(如果$$$t_i-1$$$ 或 $$$t_i+1$$$ 在数组边界内)到数组 $$$b$$$ 的右端。然后我们将元素 $$$a_{t_i+1}, \ldots, a_n$$$ 向左移动以填充空白。

给出初始排列 $$$a_1, a_2, \ldots, a_n$$$ 和结果数组 $$$b_1, b_2, \ldots, b_k$$$。数组 $$$b$$$ 的所有元素都是不同的。计算索引 $$$t_1, t_2, \ldots, t_k$$$ 模 $$$998\,244\,353$$$ 的可能序列数。

输入

每个测试包含多个测试用例。第一行包含一个整数$$$t$$$ ($$$1 \le t \le 100\,000$$$),表示测试用例的数量,后面是测试用例的描述。

每个测试用例的第一行包含两个整数 $$$n, k$$$ ($$$1 \le k < n \le 200\,000$$$):数组 $$$a$$$ 和 $$$b$$$ 的大小。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$):$$$a$$$ 的元素。 $$$a$$$ 的所有元素都是不同的。

每个测试用例的第三行包含 $$$k$$$ 整数 $$$b_1, b_2, \ldots, b_k$$$ ($$$1 \le b_i \le n$$$):$$$b$$$ 的元素。 $$$b$$$ 的所有元素都是不同的。

所有测试用例中所有 $$$n$$$ 的总和保证不超过 $$$200\,000$$$。

输出

对于每个测试用例,打印一个整数:可能序列的数量以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

3
5 3
1 2 3 4 5
3 2 5
4 3
4 3 2 1
4 3 1
7 4
1 4 7 3 6 2 5
3 2 4 5

输出 #1

2
0
4

注意

$$$\需要{取消}$$$

让我们表示为 $$$a_1 a_2 \ldots \cancel{a_i} \underline{a_{i+1}} \ldots a_n \rightarrow a_1 a_2 \ldots a_{i-1} a_{i+1} \ldots a_{n-1}$$$ 对索引为 $$$i$$$ 的元素的操作:删除元素$$$a_i$$$ 来自数组 $$$a$$$ 并将元素 $$$a_{i+1}$$$ 附加到数组 $$$b$$$。

在第一个示例测试中,可以使用以下两个选项来生成给定数组 $$$b$$$:

- $$$1 2 \underline{3} \cancel{4} 5 \rightarrow 1 \underline{2} \cancel{3} 5 \rightarrow 1 \cancel{2} \underline{5} \rightarrow 1 2$$$; $$$(t_1, t_2, t_3) = (4, 3, 2)$$$;
- $$$1 2 \underline{3} \cancel{4} 5 \rightarrow \cancel{1} \underline{2} 3 5 \rightarrow 2 \cancel{3} \underline{5} \rightarrow 1 5$$$; $$$(t_1, t_2, t_3) = (4, 1, 2)$$$。

在第二个示例测试中,无论使用何种操作,都不可能实现给定的数组。这是因为,在第一个应用程序中,我们删除了 $$$4$$$ 旁边的元素,即数字 $$$3$$$,这意味着它无法在第二步中添加到数组 $$$b$$$ 中。

在第三个示例测试中,有四个选项来实现给定数组 $$$b$$$:

- $$$1 4 \cancel{7} \underline{3} 6 2 5 \rightarrow 1 4 3 \cancel{6} \underline{2} 5 \rightarrow \cancel{1} \underline{4} 3 2 5 \rightarrow 4 3 \cancel{2} \underline{5} \rightarrow 4 3 5$$$;
- $$$1 4 \cancel{7} \underline{3} 6 2 5 \rightarrow 1 4 3 \cancel{6} \underline{2} 5 \rightarrow 1 \underline{4} \cancel{3} 2 5 \rightarrow 1 4 \cancel{2} \underline{5} \rightarrow 1 4 5$$$;
- $$$1 4 7 \underline{3} \cancel{6} 2 5 \rightarrow 1 4 7 \cancel{3} \underline{2} 5 \rightarrow \cancel{1} \underline{4} 7 2 5 \rightarrow 4 7 \cancel{2} \underline{5} \rightarrow 4 7 5$$$;
- $$$1 4 7 \underline{3} \cancel{6} 2 5 \rightarrow 1 4 7 \cancel{3} \underline{2} 5 \rightarrow 1 \underline{4} \cancel{7} 2 5 \rightarrow 1 4 \cancel{2} \underline{5} \rightarrow 1 4 5$$$;