https://www.luogu.org/problemnew/solution/P4778
非常好的题目，囊括了乘法加法原理和多重集合排列，虽然最后使用一个结论解出来的。。
给定一个n的排列，用最少的次数将排列变成单调递增
请问这样的操作有多少种
套路：位置i向位置p[i]连单向边，最后会形成l个环
先来考虑单个环：
引理：将长度为len的环拆成len个自环至少操作len-1次
套路：
一个数对应有且仅有一个位置，且一个位置有且仅有一个数
这就意味着整个图上每个点入度出度都为1
也就意味着图上的环都是简单环
于是DFS找环并统计长度可以用很简单的代码实现
每次交换操作实际上是交换边，在单向边组成的环中交换任意两条边后必定形成两个独立的环
即每次交换操作会将len的环拆成长度为x，y的两环
那么考虑有多少种拆法T(x,y)=(x==y?x:x+y)种拆分方式
设F[len]为将长度len的环拆成len个自环的操作方法数
显然有F[len]=sum{先拆成(i,len-i)的方法数}
那么先拆成(i,len-i)的方法数=T(i,len-i)*F[i]*F[len-i]*step(i,len-i)
由于把长为i的环拆成自环要i-1步，长len-i的环拆成自环要len-i-1步，这些步数可以先后穿插，但是一个环集合内自己的步数本可以打乱，所以等价于可重集合的排列数
由多重集的排列数，总共有step(i,len-i)=(len-2)!/(i-1)!*(len-i-1)! 种步数
所以最后一个长为len的环的公式是
F[len]=sum:T(i,len-i)*F[i]*F[len-i]*(len-2)!/(i-1)!*(len-i-1)!
所以最终答案是所有环相乘 ,再乘可重集合的排列数，即环于环相乘时步数也是可以先后穿插的！
事实上，有F[len]=len^(len-2)的结论