problem
一次操作指随意选定 \(x,y\) 并交换 \(a_x,a_y\)，请问有多少种方案，能用最少的操作次数重排一个排列 \(a\)？\(n\leq 10^5,P=10^9+7\)。
solution 0
连边 \(i\to a_i\)，这是一张可以发起反攻的有向图，里面有很多个环，我们称这样的环为置换环。
引理一：对于一个 \(n\) 的置换环，完成对它的排序需要 \(n-1\) 次操作。
我们求出一个 \(f_i\) 表示大小为 \(i\) 的置换环排序的方案数，这是后文重点讨论内容，略之。
求出所有的置换环。因为环与环之间互不影响，相当于操作序列也互不影响，我们可以随意打乱环与环的相对顺序，这是多重集排列数（介绍见 ZROI371），记一个环的大小为 \(b_i\)，则：
\[ans=\prod_i f_{b_i}\cdot \frac{\left(\sum_i(b_i-1)\right)!}{\prod_i (b_i-1)!}. \]到这里复杂度还是线性的。