PERMUT1 - Permutations
题意翻译
在一个有n个元素(1~n)的序列中,**查找这个序列的全排列中一共有多少个排列含有k个逆序对。**
比如当n=4,k=1时,一共有3个排列含有1个逆序对
(友情提示:1243、1324、2134)
### 输入格式:
第一行输入一个d(1<=d<=10),表示一共有d组数据。
对于每组数据,会输入整数n(1<=n<=12) 和整数k(0<=k<=98)
### 输出格式
每行输出每组数据的答案。
题目描述
Let A = \[a $ _{1} $ ,a $ _{2} $ ,...,a $ _{n} $ \] be a permutation of integers 1,2,...,n. A pair of indices (i,j), 1<=i<=j<=n, is an _inversion_ of the permutation A if a $ _{i} $ >a $ _{j} $ . We are given integers n>0 and k>=0. What is the number of n-element permutations containing exactly k inversions?
For instance, the number of 4-element permutations with exactly 1 inversion equals 3.
### Task
Write a program which for each data set from a sequence of several data sets:
- reads integers n and k from input,
- computes the number of n-element permutations with exactly k inversions,
- writes the result to output.
输入输出格式
输入格式
The first line of the input file contains one integer d, 1<=d<=10, which is the number of data sets. The data sets follow. Each data set occupies one line of the input file and contains two integers n (1<=n<=12) and k (0<=k<=98) separated by a single space.
输出格式
The i-th line of the output file should contain one integer - the number of n-element permutations with exactly k inversions.
输入输出样例
输入样例 #1
1
4 1
输出样例 #1
3