《程序设计基础二》类的设计部分练习题目:1432--1446,运算符重载部分练习题目:1447--1461

Problem 1994. -- 冒泡排序计数

1994: 冒泡排序计数

Time Limit: 1 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 8  Accepted: 1
[Submit][Status][Web Board]

Description

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

Input

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

数据规模和约定

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

Output

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

Sample Input

3
3 0
3 1
3 2

Sample Output

1
3
2

[Submit][Status][Web Board]