Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

公式的一种解释

Posted by sule at 2010-05-15 15:04:10 on Problem 3761
每个排列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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator