题解：排列周期与素数幂次的计算

---

问题分析

本题要求计算所有 $N!$ 个排列 $A$ 的周期（即返回初始排列所需操作次数）的乘积。排列 $A$ 的周期等于其循环分解中各循环长度的最小公倍数（LCM）。

我们需要计算：

$$\prod_{A \in S_N} \text{period}(A) \bmod M$$

其中 $M$ 是给定的质数。

---

关键观察

1. 问题转化

设一个排列的循环分解为若干个循环，长度分别为 $l_1, l_2, \dots, l_k$，则周期为 $\text{lcm}(l_1, l_2, \dots, l_k)$。

由于我们需要计算所有排列的周期乘积，可以对每个素数 $p$ 分别考虑，计算 $p$ 在最终答案中的指数。

2. 素数 $p$ 的贡献

对于素数 $p$，我们需要计算在所有排列中，$p$ 的幂次 $\text{ord}_p(\text{lcm}(\cdots))$ 的总和。

设 $p^e$ 是某个排列周期中 $p$ 的最高幂次。这意味着存在一个循环长度被 $p^e$ 整除，但没有循环长度被 $p^{e+1}$ 整除。

---

算法框架

第一步：预处理阶乘

预处理 $ml[i] = i \cdot (i+1) \cdots n \bmod (M-1)$，用于后续计算。

第二步：枚举素数

对于每个素数 $p \le n$，计算 $p$ 在答案中的总指数 $c$。

第三步：分类计算

对于素数 $p$，根据 $p$ 是否整除 $M-1$ 采用不同的计算方法：

情况1：$p \mid (M-1)$ 此时 $p$ 在模 $M-1$ 下没有逆元，需要特殊处理。

情况2：$p \nmid (M-1)$ 此时 $p$ 在模 $M-1$ 下有逆元，可以使用标准方法计算。

第四步：计算每个 $p^e$ 的贡献

对于每个 $e \ge 1$，令 $m = p^e$，$g = \lfloor n/m \rfloor$。我们需要计算所有排列中，至少有一个循环长度被 $m$ 整除，但没有循环长度被 $m \cdot p$ 整除的情况数。

这可以通过容斥原理计算：

• 首先计算至少有一个循环长度被 $m$ 整除的排列数
• 减去至少有一个循环长度被 $m \cdot p$ 整除的排列数

第五步：组合计数

计算有多少排列满足某些循环长度被特定数整除，这涉及到排列与划分的计数公式。对于 $g = \lfloor n/m \rfloor$，至少有一个循环长度被 $m$ 整除的排列数为：

$$n! - \frac{n!}{(m)^g \cdot g!} \cdot \prod_{i=1}^g (mi-1) $$

其中：

• $n!$ 是总排列数
• $\frac{n!}{(m)^g \cdot g!}$ 是将 $gm$ 个元素分成 $g$ 个长度为 $m$ 的循环的方案数
• $\prod_{i=1}^g (mi-1)$ 是 $g$ 个长度为 $m$ 的循环的排列方式数

第六步：最终计算

对于每个素数 $p$，将其总指数 $c$ 累加到答案中：

$$\text{ans} = \prod_{p \le n} p^{c} \bmod M$$

---

复杂度分析

• 时间复杂度：$O(n \log n)$
  • 素数筛法：$O(n \log \log n)$
  • 对每个素数 $p$，计算其所有幂次 $p^e$ 的贡献：$O(\log_p n)$
  • 总复杂度约为 $O(n \log n)$
• 空间复杂度：$O(n)$

对于 $n \le 7500$ 的数据范围完全可行。

---

总结

本题是一道组合计数与数论结合的难题，主要考察：

1. 问题分解能力：将复杂的周期乘积问题分解为素数幂次的计算
2. 容斥原理应用：处理"至少一个循环满足条件"的计数
3. 模运算技巧：在模 $M-1$ 下进行计算（利用费马小定理）
4. 特殊情况处理：处理 $p \mid (M-1)$ 时逆元不存在的情况

算法的核心在于：

• 认识到周期是循环长度的 LCM，从而可以按素数分解
• 使用容斥原理精确计算满足特定条件的排列数
• 巧妙处理模 $M-1$ 下的运算（因为最终指数要对 $M-1$ 取模，由费马小定理）

这种"将乘积问题分解为素数幂次和"的方法是解决此类数论组合问题的经典思路，但本题需要细致的容斥和模运算处理，体现了较高的思维难度和实现技巧。