问题 21464 --冒泡排序计数

21464: 冒泡排序计数

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

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

输出

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

样例输入

3
3 0
3 1
3 2

样例输出

1
3
2

来源

 

[提交][状态]