P11563 【MX-X7-T4】[LSOT-3] 命运

原题链接：。 >「这里书写着世界的『命运』」$\\$ 「当记载在此的未来成为真实之时」$\\$ 「我的珍爱 就会变成『永远』了吧」

我们在题目描述的最后提供了可以帮助理解题意的形式化题意。 Momoka 的一生中有 $n$ 个决定人生的事件，编号为 $1 \sim n$。命运的轨迹已经注定，会被第 $i$ 个事件影响的是第 $a_i$ 个事件，$a_i$ 互不相同。一个事件可能会影响过去，也可能会影响未来，甚至可以影响事件本身。 但是，因为 Momoka 的特殊能力，她的经历并不完全按照她的命运轨迹执行。有一些事件经历之后，原本应该被影响的事件不再被影响，转而影响命运轨迹中描述的会影响这个事件的事件。Momoka 的日记记录了她所经历的事件，日记可以看成是一个序列 $p$，$p_i$ 表示 Momoka 经历了第 $i$ 个事件后影响了事件 $p_i$。 Ringo 获得了日记本，她想要通过日记本来完成 M 计划。按照计划，她需要按照 Momoka 的命运轨迹来规划自己的人生。得到 Momoka 的日记之后，她想要知道 Momoka 原本的命运轨迹可能的方案数是多少。答案对 $998244353$ 取模。 **【形式化题意】** 给定一个长度为 $n$ 的序列 $p_1, \ldots, p_n$（未必为排列），保证 $1 \le p_i \le n$。求满足以下条件的**排列** $a_1, \ldots, a_n$ 的个数，对 $998244353$ 取模： > 对每个 $1 \le i \le n$，都有 $a_i=p_i$ 或者 $a_{p_i}=i$ 成立。

无

无

**【样例解释 #1】** 有以下六种可能的命运轨迹：`2 3 1 5 4`、`2 3 4 5 1`、`2 3 5 1 4`、`3 1 2 5 4`、`4 1 2 5 3`、`5 1 2 3 4`。 **【数据范围】** **本题采用捆绑测试。** - 子任务 1（15 分）：$n\le 10$。 - 子任务 2（15 分）：序列 $p$ 中 $1$ 的个数 $\ge \frac{n}{5}$。 - 子任务 3（15 分）：序列 $p$ 是排列。 - 子任务 4（25 分）：对于所有 $i,j$ 满足 $i\ne j\wedge p_i=j\wedge p_j=i$，都存在至少一个 $k\ne i\wedge k\ne j$ 满足 $p_k=i \vee p_k=j$。 - 子任务 5（30 分）：无特殊性质。 对于全部的数据，$1\le n\le 10^6$，$1\le p_i\le n$。