PermutationForces II

题意翻译

给定一个长度为 $n$ 的**排列** $a$，你可以对排列进行 $n$ 次操作，对于第 $i$ 次操作，你可以： - 选择一组**值** $x,y\in[i, \min(i+s, n)]$，并交换 $x$ 和 $y$ 的**位置**，特别的若 $x=y$ 则视为不变。 给定一个有空缺的长度为 $n$ 的**排列** $b$（空缺用 `-1` 表示），求在空缺处填入一些值使得 $a$ 能通过 $n$ 次操作变成 $b$ 的填法方案数，答案对 $998244353$ 取模。 共 $T\ (1\le T\le1000)$ 组询问，保证 $\sum n\le2\times10^5$。

题目描述

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 $ .

输入输出格式

输入格式

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 $ .

输出格式

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 $ .

输入输出样例

输入样例 #1

6
3 1
2 1 3
3 -1 -1
3 2
2 1 3
3 -1 -1
4 1
1 4 3 2
4 3 1 2
6 4
4 2 6 3 1 5
6 1 5 -1 3 -1
7 4
1 3 6 2 7 4 5
2 5 -1 -1 -1 4 -1
14 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

输出样例 #1

1
2
0
2
12
331032489

说明

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 $ .</p><p>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 $ . </p><p>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$.

**题目大意：**

给定一个长度为 $ n $ 的排列 $ a $，你可以对排列进行 $ n $ 次操作，对于第 $ i $ 次操作，你可以：

- 选择一组值 $ x, y \in [i, \min(i+s, n)] $，并交换 $ x $ 和 $ y $ 的位置，特别的若 $ x=y $ 则视为不变。

给定一个有空缺的长度为 $ n $ 的排列 $ b $（空缺用 `-1` 表示），求在空缺处填入一些值使得 $ a $ 能通过 $ n $ 次操作变成 $ b $ 的填法方案数，答案对 $ 998244353 $ 取模。

共 $ T \ (1 \le T \le 1000) $ 组询问，保证 $ \sum n \le 2 \times 10^5 $。

**输入输出数据格式：**

**输入格式：**
- 第一行包含一个整数 $ t $（$ 1 \le t \le 1000 $）——测试用例的数量。
- 每个测试用例包含三行：
- 第一行包含两个整数 $ n $ 和 $ s $（$ 1 \le n \le 2 \times 10^5 $；$ 1 \le s \le 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 $ 的元素都是不同的。

**输出格式：**
- 对于每个测试用例，输出一个整数——填充排列 $ b $ 的方式数，使得可以使用力量 $ s $ 将 $ a $ 变成 $ b $，模 $ 998244353 $。**题目大意：** 给定一个长度为 $ n $ 的排列 $ a $，你可以对排列进行 $ n $ 次操作，对于第 $ i $ 次操作，你可以： - 选择一组值 $ x, y \in [i, \min(i+s, n)] $，并交换 $ x $ 和 $ y $ 的位置，特别的若 $ x=y $ 则视为不变。 给定一个有空缺的长度为 $ n $ 的排列 $ b $（空缺用 `-1` 表示），求在空缺处填入一些值使得 $ a $ 能通过 $ n $ 次操作变成 $ b $ 的填法方案数，答案对 $ 998244353 $ 取模。 共 $ T \ (1 \le T \le 1000) $ 组询问，保证 $ \sum n \le 2 \times 10^5 $。 **输入输出数据格式：** **输入格式：** - 第一行包含一个整数 $ t $（$ 1 \le t \le 1000 $）——测试用例的数量。 - 每个测试用例包含三行： - 第一行包含两个整数 $ n $ 和 $ s $（$ 1 \le n \le 2 \times 10^5 $；$ 1 \le s \le 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 $ 的元素都是不同的。 **输出格式：** - 对于每个测试用例，输出一个整数——填充排列 $ b $ 的方式数，使得可以使用力量 $ s $ 将 $ a $ 变成 $ b $，模 $ 998244353 $。