Cards

题目描述

有 $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$ 至少出现在被选择的某张卡片的某一面上。

输入格式

输入由标准输入按以下格式给出： $N$ $P_1$ $P_2$ $\ldots$ $P_N$ $Q_1$ $Q_2$ $\ldots$ $Q_N$

输出格式

输出答案。

3
1 2 3
2 1 3

3

5
2 3 5 4 1
4 2 1 3 5

12

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

1

提示

$1 \leq N \leq 2\times 10^5$ $1 \leq P_i,Q_i \leq N$ $P$ 和 $Q$ 是 $(1, 2, \dots, N)$ 的置换。 输入中的所有值都是整数。例如，如果你选择卡片 $1$ 和 $3$，那么 $1$ 写在卡片 $1$ 的正面，$2$ 写在卡片 $1$ 的背面，$3$ 写在卡片 $3$ 的正面，所以该组合满足条件。 满足条件的选择共有 $3$ 种：$\{1,3\},\{2,3\},\{1,2,3\}$。

标签: AtCoder|abc247F

来源

AtCoder|abc247F