5099 - 冒泡排序计数

考虑冒泡排序的一种实现。
　　bubble-sort (A[], n)
　　> round = 0
　　> while A is not sorted
　　> > round := round + 1
　　> > for i := 1 to n - 1
　　> > > if (A[i] > A[i + 1])
　　> > > > swap(A[i], A[i + 1])
　　求1 .. n的排列中，有多少个排列使得A被扫描了K遍，亦即算法结束时round == K。

　　答案模20100713输出。

输入包含多组数据。每组数据为一行两个整数N，K。

对每组数据，输出一行一个整数表示答案。

数据规模和约定

　　T <= 10 ^ 5。
　　1 <= K < N < 10 ^ 6。

锦囊1

挖掘试题的性质，使用组合公式求解。

锦囊2

注意到一个性质：对排列P，设C[i]表示P[1 .. i - 1]中大于P[i]的数的个数，则我们只需要统计使得max(C[i]) = K的P的个数。因为可以注意到在每次扫描中，新的C'[i] = max(0, C[i] - 1)，而C[1 .. n]均为零是排列有序的充要条件。 考虑这一统计。我们尝试统计max(C[i]) <= K的排列个数ans(K)，之后ans(K) - ans(K - 1)即为所求。 考虑max(C[i]) <= K的排列的构造方法。从空序列开始，我们以任意顺序插入最大的K个数，于是这一部分的方案数为K!。之后，首先插入第K + 1大的数，它可以插入在任意位置；插入第K + 2大的数时，由于它的位置的C值不能超过K，而现有的数都比它大，它只能插入在前K个数之间的K + 1个位置之一；第K + 3大至第N大的数的插入与此同理。因此，插入后N - K个数的方案为(K + 1) ^ (N - K)。所以ans(K) = K! * (K + 1) ^ (N - K)，原题所求为K! * ((K + 1) ^ (N - K) - K ^ (N - K)).

蓝桥杯