F - 2SAT ?
Earlgray
2.5
s
1024
MB
600
点
問題文
整数 $N$ と数列 $X = (X_1,\ldots,X_N) ,Y = (Y_1,\ldots,Y_N)$ が与えられます。
以下の条件を満たす長さ $N$ の数列 $(A_1,\ldots,A_N)$ の個数を $998244353$ で割った余りを求めてください。
- $A_i = X_i$ または $A_i = Y_i$ が成立する
- $i\neq j$ ならば $A_i \neq A_j$
制約
- 入力は全て整数
- $1 \leq N \leq 3×10^5$
- $1 \leq X_i \leq 10^9$
- $1 \leq Y_i \leq 10^9$
部分点
この問題には部分点が設定されています。
以下の制約を満たすデータセットに正解した場合は $300$ 点が与えられます。
- 入力は全て整数
- $1 \leq N \leq 3×10^5$
- $1 \leq X_i \leq N$
- $1 \leq Y_i \leq N$
入力
$N$
$X_1\space X_2 \space \ldots \space X_N$
$Y_1\space Y_2 \space \ldots \space Y_N$
出力
答えを1行に出力してください。
入力例 1
4
1 2 3 4
2 1 4 3
出力例 1
4
条件を満たす数列は
$(1,2,3,4)$
$(2,1,3,4)$
$(1,2,4,3)$
$(2,1,4,3)$
の 4 通りなので $4$ と出力します。
入力例 2
4
1 1 1 1
2 1 4 3
出力例 2
1
条件を満たす数列は $(2,1,4,3)$ の 1 通りです。
制約上 $X_i = Y_i$ となるような入力も与えられます。
入力例 3
3
1 1 1
1 1 2
出力例 3
0
条件を満たす数列が存在しないケースもあります。
入力例 4
5
1 2 3 4 5
167772161 377487361 469762049 595591169 645922817
出力例 4
32
本ケースは部分点の制約に含まれません。