CF1442B Identify the Operations

给定一个排列 $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$ 的元素，所有元素互不相同。 第三行包含 $k$ 个整数 $b_1, b_2, \ldots, b_k$（$1 \le b_i \le n$），表示数组 $b$ 的元素，所有元素互不相同。 所有测试用例中 $n$ 的总和不超过 $200\,000$。

对于每个测试用例，输出一个整数，表示可能的下标序列数量，对 $998\,244\,353$ 取模。

$\require{cancel}$ 我们用 $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$ 中移除元素 $a_i$，并将元素 $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$。 由 ChatGPT 4.1 翻译