题解

思路

1. 从数组到内向基环森林

把每个下标视为一个点，并连有向边 $i\to a_i$。每个点恰有一条出边，因此每个弱连通块都是一棵内向基环树：一个有向环上挂着若干棵指向环的树。

若当前存在 $i\to x\to y$，选择 $i$ 操作后，$x$ 位置上的数与 $i$ 位置上的数交换，图中对应关系变为

$$i\to y,\qquad x\to x.$$

可以把这次操作理解为给原图中的边 $i\to x$ 打标记。之后从某个点出发时，连续跨过已标记边，遇到的第一条未标记边决定它在最终数组中的指向。

2. 标记方案与最终数组

设点 $u$ 的原始入度为 $d_u$。

指向同一个点 $u$ 的入边中至多标记一条：一旦其中一条边的操作使 $u$ 变为自环，再对另一条指向 $u$ 的边操作不会产生新的有效变化。因此，对每个点 $u$，可以选择“不标记任何入边”，或者选择 $d_u$ 条入边之一，表面上共有 $d_u+1$ 种选择。

这些选择在树边上彼此独立，且每个合法标记方案唯一确定最终数组。

3. 环上的唯一冲突

若一个环上的所有约束最终都把环中每个点变为自环，则不同的“最后一步”标记会得到同一个最终数组。对一个环 $C$：

• 不考虑重复时，环上各点贡献 $\prod_{u\in C}(d_u+1)$；
• 重复计算的数量恰为 $\sum_{u\in C}d_u$。

所以该环整体贡献

$$\prod_{u\in C}(d_u+1)-\sum_{u\in C}d_u.$$

不在环上的点仍独立贡献 $d_u+1$。最终答案为

$$\left(\prod_{u\notin\text{cycle}}(d_u+1)\right) \left(\prod_{C}\left(\prod_{u\in C}(d_u+1)-\sum_{u\in C}d_u\right)\right) \pmod{10^9+7}.$$

做法

4. 线性识别环点

先统计每个点的入度，把所有入度为零的点加入队列并不断删除。删除一个点 $u$ 时，令 $a_u$ 的当前入度减一；新变为零的点继续入队。

删除结束后，未删除的点恰好是所有有向环上的点。遍历每个环即可计算上式。

5. 子任务算法

• 子任务 1：对全部可达数组进行 BFS。每个状态枚举所有 $i$ 并执行一次交换，复杂度上界为 $O(n\cdot n!)$。
• 子任务 2：从每个起点独立沿出边寻找环，使用 $O(n^2)$ 时间标记所有环点，再套用计数公式。
• 子任务 3：倍增计算每个点走 $2^k\ge n$ 步后的终点。所有这些终点的集合恰为环点集合，再套用计数公式。
• 子任务 4：用拓扑剥离在线性时间内找出全部环点。

复杂度

• 子任务 1 的时间复杂度为 $O(n\cdot n!)$，空间复杂度为 $O(n\cdot n!)$。
• 子任务 2 的时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。
• 子任务 3 的时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。
• 子任务 4 的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。