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

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

hide comments
2018-02-11 05:26:27
You can solve it using bitmask DP.
2017-09-16 13:49:46
A good question. Feel free to think as you wish. Dont stick to whats mentioned in the comments! :-)
2017-03-26 19:32:12
can be solved without dp also !



for each i in [1,n-1], let S(i) = number of inversions contributed by ith element (a[i] > a[j] && i < j) in all possible permutations.

S(i) always has the range : [0,n-i]

so the problem changes to : finding number solution for the following equation,

S(1) + S(2) ......... + S(n-1) = k,

with given constraints we can solve this without TLE (think about this!!) ,give it a try :)
2017-03-16 11:55:56
Very nice question!!
2017-02-11 10:31:58
I did simple recursion without DP and it didn't TLE! Very un-strict TL :/
2017-02-01 16:13:16
OK, I've been writing cases and doing the permutations by hand to prove my algorithm. It works fine according to my understanding of the problem, but maybe that's what's wrong, maybe I just don't get the problem. For n = 7, k = 2, answer = 10? n = 7, k = 3, answer = 4? n = 8, k = 3, answer = 10? Any difficult/special test cases I'm missing maybe? When k = 0, answer = 1? when k > n (can that be a test case?) answer = 0? I don't need help with the algorithm, just with properly understanding the problem. Thanks.
2017-01-20 19:13:59
Try with bitmasking :p
2017-01-02 12:43:56
Nice and Easy!
2016-06-06 17:08:31
Why TLE??My comlexity is just O(d*(2^n)*n)!!!
2016-05-30 13:21:47
think dp .....it will make this easy :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.