← 返回题目列表

Codeforces · 2064/E

E. Mycraft 沙排序

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

Steve 有一个排列$$$^{\text{*}}$$$ $$$p$$$ 和一个数组 $$$c$$$,长度均为 $$$n$$$。 Steve 希望对排列 $$$p$$$ 进行排序。

史蒂夫有无限量的彩色沙块,他利用它们发现了一种基于物理的方法来对数字数组进行排序,称为重力排序。也就是说,要对 $$$p$$$ 执行重力排序,Steve 将执行以下操作:

  • 对于所有$$$i$$$,使得$$$1 \le i \le n$$$,将一个颜色为$$$c_i$$$的沙块放置在位置$$$(i, j)$$$,对于所有$$$j$$$,其中$$$1 \le j \le p_i$$$。这里,位置$$$(x, y)$$$表示从顶部算起第$$$x$$$行和从左边算起第$$$y$$$列中的单元格。
  • 对阵列施加向下的重力,使所有沙块只要能落下就落下。
第三个测试用例的重力排序示例。 $$$p = [4, 2, 3, 1, 5]$$$, $$$c = [2, 1, 4, 1, 5]$$$

Alex 在执行重力排序后查看 Steve 的沙块,想知道有多少对数组 $$$(p',c')$$$(其中 $$$p'$$$ 是排列)会产生相同的沙子布局。请注意,原始数组 $$$(p, c)$$$ 将始终被计算在内。

请为 Alex 计算这个。由于这个数字可能很大,因此输出它对 $$$998\,244\,353$$$ 取模。

$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现了两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有一个$$$4$$$)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组的长度。

每个测试用例的第二行包含 $$$n$$$ 不同 上面写着 整数 $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i \le n$$$) — $$$p$$$ 的元素。

以下行包含 $$$n$$$ 整数 $$$c_1,c_2,\ldots,c_n$$$ ($$$1 \le c_i \le n$$$) — $$$c$$$ 的元素。

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

输出

对于每个测试用例,输出 Steve 可以开始使用的数组对的数量 $$$(p', c')$$$,以 $$$998\,244\,353$$$ 为模。

示例

输入
复制

4
1
1
1
5
5 3 4 1 2
1 1 1 1 1
5
4 2 3 1 5
2 1 4 1 5
40
29 15 20 35 37 31 27 1 32 36 38 25 22 8 16 7 3 28 11 12 23 4 14 9 39 13 10 30 6 2 24 17 19 5 34 18 33 26 40 21
3 1 2 2 1 2 3 1 1 1 1 2 1 3 1 1 3 1 1 1 2 2 1 3 3 3 2 3 2 2 2 2 1 3 2 1 1 2 2 2

输出
复制

1
120
1
143654893

注意

第二个测试用例如下所示。

第二个测试用例的重力排序。

可以证明$$$p$$$的排列会产生相同的结果,并且$$$c$$$必须等于$$$[1,1,1,1,1]$$$(因为所有沙子必须是相同的颜色),所以答案是$$$5! = 120$$$。

第三个测试用例如上面的语句所示。可以证明,没有其他数组$$$p$$$和$$$c$$$会产生相同的最终结果,所以答案是$$$1$$$。