PERMUT1  Permutations
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 nelement permutations containing exactly k inversions?
For instance, the number of 4element 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 nelement 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 ith line of the output file should contain one integer  the number of nelement permutations with exactly k inversions.
Example
Sample input: 1 4 1 Sample output: 3
hide comments
salman3007:
20181026 20:18:35
one of the best problem i ever had on dp... 

be1035016:
20180628 15:32:34
good problem:)


sherlock11:
20180530 20:26:29
func(n,k)=summation func(n1,ki)...........and then AC:) 

vsr625:
20180211 05:26:27
You can solve it using bitmask DP. 

rohit1507:
20170916 13:49:46
A good question. Feel free to think as you wish. Dont stick to whats mentioned in the comments! :) 

t_s_vedha29:
20170326 19:32:12
can be solved without dp also !


rishi_07:
20170316 11:55:56
Very nice question!! 

coderaashir:
20170211 10:31:58
I did simple recursion without DP and it didn't TLE! Very unstrict TL :/ 

taiken:
20170201 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. 

strangerx:
20170120 19:13:59
Try with bitmasking :p 
Added by:  adrian 
Date:  20040622 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  III Polish Collegiate Team Programming Contest (AMPPZ), 1998 