分数: 400 点
问题陈述
让 S 是由所有整数组成的集合 1 通过 N.
f 是一个函数 S to S。你被赋予了价值观 f(1), f(2), \cdots, f(N) as f_1, f_2, \cdots, f_N.
求模数 998244353,非空子集 T of S 满足以下两个条件:
-
对于每个 a \in T, f(a) \in T.
-
对于每个 a, b \in T, f(a) \neq f(b) if a \neq 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),第二个条件始终满足,但第一个条件需要 T 包含 1 和 2 同时进行。
示例输入 2
2 1 1
示例输出 2
1
我们有 f(1) = f(2) = 1。第一个条件需要 T 包含 1,第二个条件禁止 T 包含 2.
示例输入 3
3 1 2 3
示例输出 3
7
我们有 f(1) = 1, f(2) = 2, f(3) = 3。这两个条件始终满足,因此所有非空子集 T 计数。