对于n个元素，假设为{0,1,...n- 1},可以发现
对于任意一个排列，假设L(i) 表示位置i上的元素的前面有多少数字比它大, 那么得到了一个L序列。
那么可以知道 交换的轮数 =  max{ L(i) } (0 <= i < n)

并且可以发现，对于所有n!种序列,其L序列满足:{[0,0],[0,1],[0,2]...[0,n-1] }...(1)

[a,b] 表示值在[a,b] 之间，包含

对于满足(1)的任意一个L序列，必然可以构造出一个对应的序列。

于是可以知道题目所求的就是max{L[i]} = k的种类数
于是我们考虑
1 * 2 * 3 .. * k  * (k + 1) ^ (n - k),就是后面的从第k项开始，全部取[0,k],前面任意取
之后扣除 1 * 2 * 3 * ... * k * k^(n - k + 1) ,就是后面第k项开始 [0,k - 1]，前面任意取

于是ans = k! * ((k + 1) ^ (n - k) - k^(n - k))

对于k!,o(1000000)预处理即可

• Re:求此题解法。。。。 (18) ivapple 2010-10-28 00:00:34