CF1770D Koxia and Game

Koxia 和 Mahiru 正在玩一个关于三个长度为 $n$ 的数组 $a$、$b$ 和 $c$ 的游戏。$a$、$b$ 和 $c$ 的每个元素都是 $1$ 到 $n$ 之间的整数。 游戏共进行 $n$ 轮。在第 $i$ 轮中，他们按如下方式操作： - 令 $S$ 为多重集 $\{a_i, b_i, c_i\}$。 - Koxia 可以从多重集 $S$ 中任选一个元素移除。 - Mahiru 从剩下的两个元素中任选一个整数。 设 $d_i$ 为 Mahiru 在第 $i$ 轮选择的整数。如果 $d$ 是一个排列 $^\dagger$，则 Koxia 获胜；否则，Mahiru 获胜。 当前，只有数组 $a$ 和 $b$ 已经确定。作为 Koxia 的忠实支持者，你想要选择一个数组 $c$，使得 Koxia 能获胜。请你计算有多少种不同的 $c$ 能让 Koxia 获胜，答案对 $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$ 取模。

在第一个测试用例中，有 $6$ 种可能的 $c$ 能让 Koxia 获胜，分别是 $[1, 2, 3]$、$[1, 3, 2]$、$[2, 2, 3]$、$[2, 3, 2]$、$[3, 2, 3]$、$[3, 3, 2]$。 在第二个测试用例中，可以证明不存在任何 $c$ 能让 Koxia 获胜。 由 ChatGPT 4.1 翻译