跳至正文
题库4150
#4150

冒泡排序计数

查看题目操作

冒泡排序计数

题目描述

考虑冒泡排序的一种实现。  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。

输出格式

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

样例

1 0
2 0
2 1
3 0
3 1
3 2
1
1
1
1
3
2

说明/提示

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

来源

蓝桥杯 算法提高