PERMUT1 - Permutations


Let A = [a1, a2, ... an] 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 ai > aj. 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.

Input

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.

Output

The i-th line of the output file should contain one integer - the number of n-element permutations with exactly k inversions.

Example

Input:
1
4 1

Output:
3

hide comments
vinupreethi93: 2020-07-07 03:08:11

https://stackoverflow.com/questions/19372991/number-of-n-element-permutations-with-exactly-k-inversions

santhosh_80: 2020-05-05 03:26:45

A good question, can be solved using DP with bitmasking

ekesh: 2020-04-27 22:53:49

The input constraints are wrong. They test cases in which n > 12. I was able to solve the problem by assuming n <= 20.

an09mous: 2020-04-14 13:28:54

Very good question. I loved solving it.

maskmanlucifer: 2020-04-05 04:35:52

nice question for beginners.

hellb0y_suru: 2020-03-22 20:52:20

@taiken
for n=7 , k=2 , answer is 20 ,
n = 7 , k=3 , answer is 49,
n = 8 , k =3 , answer is 76.

whyamievenhere: 2018-12-20 16:00:30

just ensure dp[1][0]==1 .. got 2 WA because of it..

salman3007: 2018-10-26 20:18:35

one of the best problem i ever had on dp...

be1035016: 2018-06-28 15:32:34

good problem:)
nice and elegant dp solution

sherlock11: 2018-05-30 20:26:29

func(n,k)=summation func(n-1,k-i)...........and then AC:)


Added by:adrian
Date:2004-06-22
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:III Polish Collegiate Team Programming Contest (AMPPZ), 1998