配点 : 500 点
問題文
1,…,N の番号がついた N 枚のカードがあり、カード i の表には Pi が、裏には Qi が書かれています。
ここで、P=(P1,…,PN) 及び Q=(Q1,…,QN) はそれぞれ (1,2,…,N) の並び替えです。
N 枚のカードから何枚かを選ぶ方法のうち、次の条件を満たすものは何通りありますか? 998244353 で割った余りを求めてください。
条件:1,2,…,N のどの数も選んだカードのいずれかに書かれている
制約
- 1≤N≤2×105
- 1≤Pi,Qi≤N
- P,Q はそれぞれ (1,2,…,N) の並び替えである
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N
P1 P2 … PN
Q1 Q2 … QN
出力
答えを出力せよ。
3
1 2 3
2 1 3
3
例えばカード 1,3 を選ぶと、1 はカード 1 の表に、2 はカード 1 の裏に、3 はカード 3 の表に書かれているため条件を満たします。
条件を満たすカードの選び方は {1,3},{2,3},{1,2,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