310001: CF1770D. Koxia and Game

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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.

Input

题意翻译

Koxia 和 Mahiru 正在玩一个游戏。游戏使用 $a,b,c$ 三个长度为 $n$ 的数组,共进行 $n$ 轮。 每一轮中,Koxia 先在 $a_i,b_i,c_i$ 中选择一个数字,Mahiru 再从未选择的两个数字中选择一个。 如果 $n$ 轮后 Mahiru 选择的数字刚好包含 $1$ 至 $n$ 中每个数字各一个(即为 $1$ 至 $n$ 的一个排列),**则 Koxia 获胜。否则,Mahiru 获胜。** 假设双方都采取最优策略,给定 $a,b$ 数组,求使得 Koxia 必胜的 $c$ 数组的个数。

Output

**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获胜。

加入题单

上一题 下一题 算法标签: