Score : $500$ points

问题陈述

有 $N$ 张卡片，编号分别为 $1,\ldots,N$。第 $i$ 张卡片正面写有 $P_i$，背面写有 $Q_i$。 这里，$P=(P_1,\ldots,P_N)$ 和 $Q=(Q_1,\ldots,Q_N)$ 是 $(1, 2, \dots, N)$ 的排列。

在满足以下条件的情况下，有多少种方法可以从这 $N$ 张卡片中选择一些卡片？请计算满足条件的方案数对 $998244353$ 取模的结果。

条件：每个数字 $1,2,\ldots,N$ 至少在一个被选中的卡片上出现。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There are $N$ cards numbered $1,\ldots,N$. Card $i$ has $P_i$ written on the front and $Q_i$ written on the back.
Here, $P=(P_1,\ldots,P_N)$ and $Q=(Q_1,\ldots,Q_N)$ are permutations of $(1, 2, \dots, N)$.

How many ways are there to choose some of the $N$ cards such that the following condition is satisfied? Find the count modulo $998244353$.

Condition: every number $1,2,\ldots,N$ is written on at least one of the chosen cards.

Constraints

• $1 \leq N \leq 2\times 10^5$
• $1 \leq P_i,Q_i \leq N$
• $P$ and $Q$ are permutations of $(1, 2, \dots, N)$.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$

$P_1$ $P_2$ $\ldots$ $P_N$

$Q_1$ $Q_2$ $\ldots$ $Q_N$

Output

Print the answer.

Sample Input 1

3
1 2 3
2 1 3

Sample Output 1

3

For example, if you choose Cards $1$ and $3$, then $1$ is written on the front of Card $1$, $2$ on the back of Card $1$, and $3$ on the front of Card $3$, so this combination satisfies the condition.

There are $3$ ways to choose cards satisfying the condition: $\{1,3\},\{2,3\},\{1,2,3\}$.

Sample Input 2

5
2 3 5 4 1
4 2 1 3 5

Sample Output 2

12

Sample Input 3

8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8

Sample Output 3

1

update @ 2024/3/10 10:36:08