Koxia and Game

题目描述

Koxia and Mahiru are playing a game with three arrays $ a $ , $ b $ , and $ c $ of length $ n $ . Each element of $ a $ , $ b $ and $ c $ is an integer between $ 1 $ and $ n $ inclusive. The game consists of $ n $ rounds. In the $ i $ -th round, they perform the following moves: - Let $ S $ be the multiset $ \{a_i, b_i, c_i\} $ . - Koxia removes one element from the multiset $ S $ by her choice. - Mahiru chooses one integer from the two remaining in the multiset $ S $ . Let $ d_i $ be the integer Mahiru chose in the $ i $ -th round. If $ d $ is a permutation $ ^\dagger $ , Koxia wins. Otherwise, Mahiru wins. Currently, only the arrays $ a $ and $ b $ have been chosen. As an avid supporter of Koxia, you want to choose an array $ c $ such that Koxia will win. Count the number of such $ c $ , modulo $ 998\,244\,353 $ . Note that Koxia and Mahiru both play optimally. $ ^\dagger $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array).

输入输出格式

输入格式

Each test consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 2 \cdot 10^4 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq {10}^5 $ ) — the size of the arrays. The second line of each test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \leq a_i \leq n $ ). The third line of each test case contains $ n $ integers $ b_1, b_2, \dots, b_n $ ( $ 1 \leq b_i \leq n $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ {10}^5 $ .

输出格式

Output a single integer — the number of $ c $ makes Koxia win, modulo $ 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

说明

In the first test case, there are $ 6 $ possible arrays $ c $ that make Koxia win — $ [1, 2, 3] $ , $ [1, 3, 2] $ , $ [2, 2, 3] $ , $ [2, 3, 2] $ , $ [3, 2, 3] $ , $ [3, 3, 2] $ . In the second test case, it can be proved that no array $ c $ makes Koxia win.

**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是一个排列，则Koxia获胜。否则，Mahiru获胜。

目前，只有数组a和b已被选定。作为Koxia的热心支持者，你想选择一个数组c，使得Koxia获胜。计算这样的c的数量，模998,244,353。

注意，Koxia和Mahiru都进行最优游戏。

**输入输出格式：**
**输入格式：**
每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤2×10^4）——测试用例的数量。测试用例描述如下。

每个测试用例的第一行包含一个整数n（1≤n≤10^5）——数组的大小。

每个测试用例的第二行包含n个整数a_1, a_2, …, a_n（1≤a_i≤n）。

每个测试用例的第三行包含n个整数b_1, b_2, …, b_n（1≤b_i≤n）。

保证所有测试用例的n之和不超过10^5。

**输出格式：**
输出一个整数——使Koxia获胜的c的数量，模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获胜。**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是一个排列，则Koxia获胜。否则，Mahiru获胜。 目前，只有数组a和b已被选定。作为Koxia的热心支持者，你想选择一个数组c，使得Koxia获胜。计算这样的c的数量，模998,244,353。 注意，Koxia和Mahiru都进行最优游戏。 **输入输出格式：** **输入格式：** 每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤2×10^4）——测试用例的数量。测试用例描述如下。 每个测试用例的第一行包含一个整数n（1≤n≤10^5）——数组的大小。 每个测试用例的第二行包含n个整数a_1, a_2, …, a_n（1≤a_i≤n）。 每个测试用例的第三行包含n个整数b_1, b_2, …, b_n（1≤b_i≤n）。 保证所有测试用例的n之和不超过10^5。 **输出格式：** 输出一个整数——使Koxia获胜的c的数量，模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获胜。