/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
1 以上 N 以下の整数すべてから成る集合を S とします．
f は S から S への関数であり，f(1), f(2), \cdots, f(N) の値が f_1, f_2, \cdots, f_N として与えられます．
S の空でない部分集合 T であって，次の両方の条件を満たすものの個数を 998244353 で割った余りを求めてください．
-
全ての a \in T について f(a) \in T である．
-
全ての a, b \in T について a \neq b ならば f(a) \neq f(b) である．
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq f_i \leq N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる．
N f_1 f_2 \ldots f_N
出力
S の空でない部分集合であって，両方の条件を満たすものの個数を 998244353 で割った余りを出力せよ．
入力例 1
2 2 1
出力例 1
1
f(1) = 2, f(2) = 1 です．f(1) \neq f(2) であるため条件の 2 つ目は常に満たしますが，1 つ目の条件より 1, 2 は同時に T に入っている必要があります．
入力例 2
2 1 1
出力例 2
1
f(1) = f(2) = 1 です．1 つ目の条件のため 1 は T に属する必要があり，さらに 2 つ目の条件により 2 は T に属することはできません．
入力例 3
3 1 2 3
出力例 3
7
f(1) = 1, f(2) = 2, f(3) = 3 です．1 つ目の条件も 2 つ目の条件も常に満たされるため，S の空でない部分集合全てが条件を満たします．
Score : 400 points
Problem Statement
Let S be a set composed of all integers from 1 through N.
f is a function from S to S. You are given the values f(1), f(2), \cdots, f(N) as f_1, f_2, \cdots, f_N.
Find the number, modulo 998244353, of non-empty subsets T of S satisfying both of the following conditions:
-
For every a \in T, f(a) \in T.
-
For every a, b \in T, f(a) \neq f(b) if a \neq b.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq f_i \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N f_1 f_2 \ldots f_N
Output
Print the number of non-empty subsets of S satisfying both of the conditions, modulo 998244353.
Sample Input 1
2 2 1
Sample Output 1
1
We have f(1) = 2, f(2) = 1. Since f(1) \neq f(2), the second condition is always satisfied, but the first condition requires T to contain 1 and 2 simultaneously.
Sample Input 2
2 1 1
Sample Output 2
1
We have f(1) = f(2) = 1. The first condition requires T to contain 1, and the second condition forbids T to contain 2.
Sample Input 3
3 1 2 3
Sample Output 3
7
We have f(1) = 1, f(2) = 2, f(3) = 3. Both of the conditions are always satisfied, so all non-empty subsets of T count.