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

时间:2022-02-01 17:05:40

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