Luogu4709 信息传递

题意：给出一个 元置换 。求有多少个置换 满足 。

答案对 取模，，时限 。

---

有意思的题。

看到置换乘积，首先把置换分解成循环表示。

单独看一个循环，有如下定理：

• 长度为 的循环在 次幂之后得到的置换有 个等大小循环。

  可以看做每个元素转动了 次。沿着某个环走，不断 再模 ，易得恰能走 步。

也就是说， 中的 个长度为 的环能对应到 中的一个环，当且仅当 。

考虑 个长度为 的小环有多少种拼合的方法。

由于拼合后是大环，先钦定第一个小环的第一个元素排在第一位。

此外,其余 个小环可以随意旋转，方案数为 。

其余 个小环之间还可以随意排列，方案数为

总的来说就是 。不妨设为 。

---

容易发现，不同大小的循环之间互不影响，我们每种大小分开考虑。

现有 个长度为 的环。

设 为使用了 个环的方案数。则 中间是 而不是 的原因：合成的各个环是无序的，不妨钦定每次必选第一个。

其中, ,所以枚举量是 级别的。

对每种大小分别计算，复杂度 。