102475: [AtCoder]ABC247 F - Cards
Description
Score : $500$ points
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
Input
题意翻译
给定 $ n $ 张卡片,每张卡片正反面各有一个数,给定每张卡片正面和反面的数,保证正面的数构成的序列,和反面的数构成的,分别均为 $ 1 $ 到 $ n $ 的排列,可以选择任意张卡片并获得其正反面的数,要求最终所有获得的数至少包含 $ 1 $ 到 $ n $ 每个数至少一次。求有多少种取法,对 $ 998244353 $ 取模。Output
得分:500分
问题描述
有N张卡片,编号为1,…,N。第i张卡片的正面写着P_i,背面写着Q_i。
其中,P=(P_1, …, P_N)和Q=(Q_1, …, Q_N)是(1, 2, …, N)的一个排列。
满足以下条件的N张卡片的选择方式有多少种?请计算答案对998244353取模。
条件:每一个数1,2,…,N都至少写在所选卡片中的一张上。
约束条件
- 1≤N≤2×10^5
- 1≤P_i,Q_i≤N
- P和Q是(1, 2, …, N)的一个排列。
- 输入中的所有值都是整数。
输入
输入通过标准输入给出以下格式:
$N$ $P_1$ $P_2$ $\ldots$ $P_N$ $Q_1$ $Q_2$ $\ldots$ $Q_N$
输出
打印答案。
样例输入1
3 1 2 3 2 1 3
样例输出1
3
例如,如果你选择卡片1和3,那么1写在卡片1的正面,2写在卡片1的背面,3写在卡片3的正面,因此这种组合满足条件。
有3种选择卡片满足条件的方式:$\{1,3\}$,$\{2,3\}$,$\{1,2,3\}$。
样例输入2
5 2 3 5 4 1 4 2 1 3 5
样例输出2
12
样例输入3
8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
样例输出3
1