| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
公式的一种解释每个排列a1a2...an唯一对应一个反序列表b1b2...bn,例如
5 9 1 8 2 6 4 7 3
有反序表
2 3 6 4 0 2 2 1 0
bj为位于j左边但大于j的元素个数
冒泡排序交换相邻元素,改变对应的反序数。如果对应的反序数大于0,则减1.
因此对一个排列使用冒泡排序的扫描次数k = max{bj}
任给一个k,求对应的排列数就是求反序数最大值为k的反序表的个数,
反序表每位上的反序数的取值范围为[0, n - i].
这样就能得到对应的反序表个数为 k! * ((k + 1)^(n - k) - k ^(n - k))
详细介绍见程序设计艺术第三卷第1节
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator