「AHOI2022」排列 题解

算法思路分析

核心数学洞察

循环值的本质：排列$P$的循环值$v(P)$等于其所有循环长度的最小公倍数（LCM）。

证明思路：

• 排列的幂运算在每个循环上相当于循环移位
• $P^{(k+1)} = P$当且仅当每个长度为$L$的循环满足$(k+1) \equiv 1 \pmod{L}$
• 即$k$是每个循环长度$L$的倍数
• 因此最小的$k$就是所有$L$的LCM

置换的循环分解

将排列视为映射$i \to a_i$，可以得到若干不相交循环：

• 每个循环：$i \to a_i \to a_{a_i} \to \cdots \to i$
• 循环长度$l_1, l_2, \ldots, l_m$
• 原排列的循环值$v(A) = \text{LCM}(l_1, l_2, \ldots, l_m)$

交换操作对循环结构的影响

情况一：同循环内交换（$f(i,j) = 0$）

若$i,j$在同一循环中，交换$A_i$和$A_j$会分裂该循环：

• 原循环：$(i, x_1, \ldots, x_p, j, y_1, \ldots, y_q)$
• 交换后分裂为：$(i, y_1, \ldots, y_q)$和$(j, x_1, \ldots, x_p)$
• 但此时$i$和$j$仍在同一连通分量，$f(i,j) = 0$

情况二：不同循环间交换（产生贡献）

若$i$在循环$C_a$(长度$L_a$)，$j$在循环$C_b$(长度$L_b$)，交换后：

• $C_a$和$C_b$合并为长度为$L_a + L_b$的新循环
• 新排列循环值 = $\text{LCM}(L_a+L_b, \text{其他所有循环长度的LCM})$

高效算法设计

步骤1：循环检测

• 使用DFS或迭代法找出所有循环
• 记录每个循环的长度和元素归属
• 时间复杂度：$O(n)$

步骤2：LCM预处理

• 对每个循环长度进行质因数分解
• 维护全局LCM的质因数分解形式
• 便于快速计算"移除某两个循环后的LCM"

步骤3：贡献计算优化

关键观察：相同长度配对的循环对贡献相同

设循环长度频次数组为$cnt[L]$，则：

• 对于长度$L_a \neq L_b$：有$cnt[L_a] \times cnt[L_b] \times L_a \times L_b$个交换对
• 对于长度$L_a = L_b$：有$\binom{cnt[L_a]}{2} \times L_a^2$个交换对

每对的贡献值：

$$\text{贡献} = \text{LCM}\left(\frac{\text{全局LCM}}{\text{LCM}(L_a,L_b)}, L_a+L_b\right) $$

步骤4：模运算处理

• 使用费马小定理计算模逆元
• 质因数分解形式下便于模运算
• 最终结果对$10^9+7$取模

复杂度分析

• 循环检测：$O(n)$
• 质因数分解：$O(n \log n)$
• 贡献计算：$O(d^2)$，其中$d$为不同循环长度的个数
  • 由于$d \leq O(\sqrt{n})$，实际效率很高
• 总体：$O(n \log n + d^2)$，可处理$n \leq 5\times 10^5$

算法亮点

1. 数学转化：将排列问题转化为数论问题
2. 批量处理：按循环长度分组，避免$O(n^2)$枚举
3. 质因数技巧：LCM的质因数分解形式便于快速计算
4. 组合计数：利用对称性减少计算量

实现要点

• 使用vector存储循环信息
• 用map记录长度频次
• 质因数分解预处理到$\sqrt{n}$
• 注意整数溢出，及时取模

这种解法充分利用了排列的代数结构和数论性质，实现了从$O(n^2)$到$O(n \log n)$的优化。