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