乘法原理，加法原理，多重集的排列数（多个系列操作穿插的排列数）进阶指南洛谷p4778

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)的结论

巴特西