找一下排列里的置换环。$k$ 步容易转换成 $1$ 步，用点 $\gcd$ 啥的推一推。这样就变成 $k=1$ 了。

考虑两个点连边会导致两个置换环之间连边，不妨设两个环大小为 $a,b$，且 $a\le b$。将两个环一号点连起来，看看后面如何循环连边，找找规律手玩两下发现能连边当且仅当 $a|b$，且方案数为 $a$。这样可以把环当点来数树。

发现如果有自环点的话已经连成树了。但是如果没有的话还需要一个环和自己连一下把森林变成树。发现只有 $len=2$ 能成功，方案数为这种环的个数。

考虑对环形成的树计数。先不考虑一个大小的环有多种，那它往环长更小的环连边是独立的，方案数很好算，枚举因数即可（此处改成枚举倍数，显然复杂度 $O(\sum \frac ni)=O(n\log n)$）。但是如果一个大小的环有多种，那这里需要考虑到同大小环之间可以连边。这时候我们发现往环长更小的环连边的总方案数是一定的，可以临时考虑成一个虚点 $0$ 表示往环长更小的环连边的方案。然后变成虚点和这些环要连成一棵树，方案数为 $a^{deg_0}\times b^{m-deg_0}$。这时候我们拿出 prufer 序列，枚举 $deg_0$，求出树的个数和总方案数，再累加。

复杂度调和级数。