CF1698E PermutationForces II

给定一个长度为 $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$ 替代。请你统计有多少种方法可以用 $1$ 到 $n$ 的整数替换 $b$ 中的每个 $-1$，使得 $b$ 是一个排列，并且可以用强度 $s$ 将 $a$ 变为 $b$。 由于答案可能很大，请输出对 $998\,244\,353$ 取模后的结果。

输入包含多组测试用例。第一行包含一个整数 $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$ 的元素。所有不等于 $-1$ 的 $b$ 中的元素互不相同。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示有多少种方法填充排列 $b$，使得可以用强度 $s$ 将 $a$ 变为 $b$，答案对 $998\,244\,353$ 取模。

在第一个测试用例中，$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$。 由 ChatGPT 4.1 翻译