#l. Cards

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l

Type: RemoteJudge

2000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面翻译

给定 $n$ 张卡片，每张卡片正反面各有一个数，给定每张卡片正面和反面的数，保证正面的数构成的序列，和反面的数构成的，分别均为 $1$ 到 $n$ 的排列，可以选择任意张卡片并获得其正反面的数，要求最终所有获得的数至少包含 $1$ 到 $n$ 每个数至少一次。求有多少种取法，对 $998244353$ 取模。

题目描述

$1,\ldots,N$ の番号がついた $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$

输出格式

答えを出力せよ。

样例 #1

样例输入 #1

3
1 2 3
2 1 3

样例输出 #1

样例 #2

样例输入 #2

5
2 3 5 4 1
4 2 1 3 5

样例输出 #2

样例 #3

样例输入 #3

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

样例输出 #3

提示

制約

$1\ \leq\ N\ \leq\ 2\times\ 10^5$
$1\ \leq\ P_i,Q_i\ \leq\ N$
$P,Q$ はそれぞれ $(1,\ 2,\ \dots,\ N)$ の並び替えである
入力に含まれる値は全て整数である

Sample Explanation 1

例えばカード $1,3$ を選ぶと、 $1$ はカード $1$ の表に、 $2$ はカード $1$ の裏に、 $3$ はカード $3$ の表に書かれているため条件を満たします。条件を満たすカードの選び方は $\{1,3\},\{2,3\},\{1,2,3\}$ の $3$ 通りです。

北辰OI提高组第2周序列问题课后练习题👍

Not Attended

Status: Done
Rule: IOI
Problem: 44
Start at: 2024-1-7 16:00
End at: 2024-2-18 8:00
Duration: 1000 hour(s)
Host: yuyongchao
Partic.: 15

#l. Cards

Cards

题面翻译

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

样例 #3

样例输入 #3

样例输出 #3

提示

制約

Sample Explanation 1

北辰OI提高组第2周序列问题课后练习题👍

Status

Development

Support

#l. Cards

Cards

题面翻译

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

样例 #3

样例输入 #3

样例输出 #3

提示

制約

Sample Explanation 1

北辰OI提高组第2周序列问题课后练习题👍

Status

Development

Support

Don't have an account?

SIGN IN