CF1698E.PermutationForces II

You are given a permutation $a$ of length $n$. Recall that permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order.

You have a strength of $s$ and perform $n$ moves on the permutation $a$. The $i$-th move consists of the following:

• Pick two integers $x$ and $y$ such that $i \leq x \leq y \leq \min(i+s,n)$, and swap the positions of the integers $x$ and $y$ in the permutation $a$. Note that you can select $x=y$ in the operation, in which case no swap will occur.

You want to turn $a$ into another permutation $b$ after $n$ moves. However, some elements of $b$ are missing and are replaced with $-1$ instead. Count the number of ways to replace each $-1$ in $b$ with some integer from $1$ to $n$ so that $b$ is a permutation and it is possible to turn $a$ into $b$ with a strength of $s$.

Since the answer can be large, output it modulo $998\,244\,353$.

你有一个长度为 $n$ 的排列 $a$。回忆一下，排列是由 $1$ 到 $n$ 的 $n$ 个互不相同的整数组成的、顺序任意的数组。

你拥有强度 $s$，并在排列 $a$ 上执行 $n$ 次操作。第 $i$ 次操作包含以下步骤：

• 选择两个整数 $x$ 和 $y$，满足 $i \leq x \leq y \leq \min(i+s,n)$，然后在排列 $a$ 中交换整数 $x$ 和 $y$ 的位置。注意，你可以在该操作中选择 $x = y$，此时不发生任何交换。

你希望经过 $n$ 次操作后将 $a$ 变为另一个排列 $b$。然而，$b$ 中某些元素缺失，被替换为 $-1$。请计算将 $b$ 中每个 $-1$ 替换为 $1$ 到 $n$ 中某个整数的方式数目，使得 $b$ 成为一个合法排列，并且存在一种方式，在强度为 $s$ 的条件下，能将 $a$ 变为该 $b$。

由于答案可能很大，请对 $998\,244\,353$ 取模输出结果。

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $s$ ($1 \leq n \leq 2 \cdot 10^5$; $1 \leq s \leq n$) — the size of the permutation and your strength, respectively.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the elements of $a$. All elements of $a$ are distinct.

The third line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le n$ or $b_i = -1$) — the elements of $b$. All elements of $b$ that are not equal to $-1$ are distinct.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $s$（$1 \leq n \leq 2 \cdot 10^5$；$1 \leq s \leq n$），分别表示排列的大小和你的力量值。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），即数组 $a$ 的元素。$a$ 的所有元素互不相同。

每个测试用例的第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \le b_i \le n$ 或 $b_i = -1$），即数组 $b$ 的元素。$b$ 中所有不等于 $-1$ 的元素互不相同。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, output a single integer — the number of ways to fill up the permutation $b$ so that it is possible to turn $a$ into $b$ using a strength of $s$, modulo $998\,244\,353$.

对于每个测试用例，输出一个整数——即填满排列 $b$ 的方案数，使得能够使用强度 $s$ 将 $a$ 变为 $b$，结果对 $998\,244\,353$ 取模。

In the first test case, $a=[2,1,3]$. There are two possible ways to fill out the $-1$s in $b$ to make it a permutation: $[3,1,2]$ or $[3,2,1]$. We can make $a$ into $[3,1,2]$ with a strength of $1$ as follows: $$[2,1,3] \xrightarrow[x=1,\,y=1]{} [2,1,3] \xrightarrow[x=2,\,y=3]{} [3,1,2] \xrightarrow[x=3,\,y=3]{} [3,1,2].$$ It can be proven that it is impossible to make $[2,1,3]$ into $[3,2,1]$ with a strength of $1$. Thus only one permutation $b$ satisfies the constraints, so the answer is $1$.

In the second test case, $a$ and $b$ the same as the previous test case, but we now have a strength of $2$. We can make $a$ into $[3,2,1]$ with a strength of $2$ as follows: $$[2,1,3] \xrightarrow[x=1,\,y=3]{} [2,3,1] \xrightarrow[x=2,\,y=3]{} [3,2,1] \xrightarrow[x=3,\,y=3]{} [3,2,1].$$ We can still make $a$ into $[3,1,2]$ using a strength of $1$ as shown in the previous test case, so the answer is $2$.

In the third test case, there is only one permutation $b$. It can be shown that it is impossible to turn $a$ into $b$, so the answer is $0$.

在第一个测试用例中，$a=[2,1,3]$。将 $b$ 中的 $-1$ 填充为一个排列共有两种可能：$[3,1,2]$ 或 $[3,2,1]$。我们可以用强度 $1$ 将 $a$ 变为 $[3,1,2]$，过程如下：

\[2,1,3\] \\xrightarrow\[x=1,\\,y=1\]{} \[2,1,3\] \\xrightarrow\[x=2,\\,y=3\]{} \[3,1,2\] \\xrightarrow\[x=3,\\,y=3\]{} \[3,1,2\].

可以证明：无法用强度 $1$ 将 $[2,1,3]$ 变为 $[3,2,1]$。因此，仅有一个排列 $b$ 满足约束条件，答案为 $1$。

在第二个测试用例中，$a$ 和 $b$ 与上一测试用例相同，但现在强度为 $2$。我们可以用强度 $2$ 将 $a$ 变为 $[3,2,1]$，过程如下：

\[2,1,3\] \\xrightarrow\[x=1,\\,y=3\]{} \[2,3,1\] \\xrightarrow\[x=2,\\,y=3\]{} \[3,2,1\] \\xrightarrow\[x=3,\\,y=3\]{} \[3,2,1\].

如前一测试用例所示，我们仍可用强度 $1$ 将 $a$ 变为 $[3,1,2]$，因此答案为 $2$。

在第三个测试用例中，仅存在一个排列 $b$。可以证明：无法将 $a$ 变为 $b$，因此答案为 $0$。