← 返回题目列表

Codeforces · 1698/E

E. 排列力 II

中文机器翻译题面 查看原题

给你一个长度为 $$$n$$$ 的排列 $$$a$$$。回想一下,排列是一个由 $$$n$$$ 不同整数组成的数组,从 $$$1$$$ 到 $$$n$$$ 以任意顺序排列。

您的实力为 $$$s$$$,并在排列 $$$a$$$ 上执行 $$$n$$$ 步。第 $$$i$$$ 步移动包含以下内容:

- 选择两个整数 $$$x$$$ 和 $$$y$$$,使得 $$$i \leq x \leq y \leq \min(i+s,n)$$$,并交换整数 $$$x$$$ 和 $$$y$$$ 在排列 $$$a$$$ 中的位置。注意,操作中可以选择$$$x=y$$$,这样就不会发生交换。

您想在 $$$n$$$ 移动后将 $$$a$$$ 转换为另一个排列 $$$b$$$。但是,$$$b$$$ 的某些元素丢失,并被替换为 $$$-1$$$。计算将 $$$b$$$ 中的每个 $$$-1$$$ 替换为 $$$1$$$ 到 $$$n$$$ 之间的某个整数的方法数量,以便 $$$b$$$ 是一个排列,并且可以将 $$$a$$$ 转换为 $$$b$$$,强度为 $$$s$$$。

由于答案可能很大,因此输出它对 $$$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$$$ 的元素。 $$$b$$$ 中不等于 $$$-1$$$ 的所有元素都是不同的。

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

输出

对于每个测试用例,输出一个整数 - 填充排列 $$$b$$$ 的方法数量,以便可以使用 $$$s$$$ 的强度将 $$$a$$$ 转换为 $$$b$$$,以 $$$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

注意

在第一个测试用例中,$$$a=[2,1,3]$$$。有两种可能的方法可以填写 $$$b$$$ 中的 $$$-1$$$ 使其成为排列:$$$[3,1,2]$$$ 或 $$$[3,2,1]$$$。我们可以将 $$$a$$$ 变为强度为 $$$1$$$ 的 $$$[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].$$$$$$ 可以证明,不可能将$$$[2,1,3]$$$变成强度为$$$1$$$的$$$[3,2,1]$$$。因此只有一种排列 $$$b$$$ 满足约束,所以答案是 $$$1$$$。

在第二个测试用例中,$$$a$$$ 和 $$$b$$$ 与之前的测试用例相同,但我们现在的强度为 $$$2$$$。我们可以将 $$$a$$$ 变为强度为 $$$2$$$ 的 $$$[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$$$。