P15596 [ICPC 2020 Jakarta R] Permutation Transformation

一个 $1 \dots N$ 的排列是一个整数数组 $P[1 \dots N]$，使得每个从 $1$ 到 $N$ 的整数在 $P[1 \dots N]$ 中恰好出现一次。对 $P[1 \dots N]$ 进行 **变换** 定义为将其改变为另一个排列 $P'[1 \dots N]$，其中对于所有 $1 \leq i \leq N$，有 $P'[i] = P[P[i]]$。 给定一个排列 $P[1 \dots N]$。你的任务是计算通过对给定排列进行零次或多次变换所能得到的不同排列的个数。 例如，令 $P[1 \dots N] = [3, 5, 1, 2, 4]$。 - 进行一次变换，$P$ 变为 $[1, 4, 3, 5, 2]$。 - 再进行一次变换，$P$ 变为 $[1, 5, 3, 2, 4]$。 - 再进行一次变换，$P$ 再次变为 $[1, 4, 3, 5, 2]$。 因此，通过进行零次或多次变换，可以得到 $3$ 个不同的排列。 1. $[3, 5, 1, 2, 4]$ 2. $[1, 4, 3, 5, 2]$ 3. $[1, 5, 3, 2, 4]$

输入第一行包含一个整数 $N$（$1 \leq N \leq 100\,000$），表示给定排列中元素的个数。下一行包含 $N$ 个整数 $P[i]$（$1 \leq P[i] \leq N$），表示该排列。保证 $P[1 \dots N]$ 中的元素互不相同。

输出一行一个整数，表示通过对给定排列进行零次或多次变换所能得到的不同排列的个数，对 $998\,244\,353$ 取模。

#### 样例 #1 解释 此为题目描述中的示例。 #### 样例 #2 解释 通过对给定排列进行零次或多次变换，可以得到 $4$ 个不同的排列。 1. $[7, 5, 1, 6, 8, 2, 3, 4]$ 2. $[3, 8, 7, 2, 4, 5, 1, 6]$ 3. $[7, 6, 1, 8, 2, 4, 3, 5]$ 4. $[3, 4, 7, 5, 6, 8, 1, 2]$ 翻译由 DeepSeek 完成