← 返回题目列表

Codeforces · 1770/D

D. Koxia 和游戏

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

Koxia 和 Mahiru 正在玩一个游戏,其中包含三个长度为 $$$n$$$ 的数组 $$$a$$$、$$$b$$$ 和 $$$c$$$。 $$$a$$$、$$$b$$$ 和 $$$c$$$ 的每个元素都是 $$$1$$$ 和 $$$n$$$ 之间的整数(包括 $$$1$$$ 和 $$$n$$$)。

游戏由 $$$n$$$ 轮组成。在第 $$$i$$$ 轮中,他们执行以下动作:

- 令 $$$S$$$ 为多重集 $$$\{a_i, b_i, c_i\}$$$。
- Koxia 根据她的选择从多重集中 $$$S$$$ 中删除了一个元素。
- Mahiru 从多重集合 $$$S$$$ 中剩余的两个整数中选择一个整数。

令 $$$d_i$$$ 为 Mahiru 在第 $$$i$$$ 轮中选择的整数。如果 $$$d$$$ 是排列$$$^\dagger$$$,则 Koxia 获胜。否则,真昼就赢了。

目前,仅选择了数组 $$$a$$$ 和 $$$b$$$。作为 Koxia 的狂热支持者,您希望选择一个数组 $$$c$$$ 以便 Koxia 获胜。计算这样的 $$$c$$$ 的数量,以 $$$998\,244\,353$$$ 为模。

请注意,Koxia 和 Mahiru 都发挥最佳状态。

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

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq {10}^5$$$) — 数组的大小。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$)。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \leq b_i \leq n$$$)。

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

输出

输出一个整数 - $$$c$$$ 的数量使 Koxia 获胜,模 $$$998\,244\,353$$$。

示例

输入 #1

2
3
1 2 2
1 3 3
5
3 3 1 3 4
4 5 2 5 5

输出 #1

6
0

注意

在第一个测试用例中,有 $$$6$$$ 可能的数组 $$$c$$$ 使 Koxia 获胜 — $$$[1, 2, 3]$$$, $$$[1, 3, 2]$$$, $$$[2, 2, 3]$$$, $$$[2, 3, 2]$$$, $$$[3, 2, 3]$$$,$$$[3,3,2]$$$。

在第二个测试用例中,可以证明没有数组 $$$c$$$ 能让 Koxia 获胜。