← 返回题目列表

AtCoder · arc114_b

B. 特殊子集

中文机器翻译题面 查看原题

分数: 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 计数。