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.


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.


Sample input:
4 1 

Sample output:

hide comments
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:)

vsr625: 2018-02-11 05:26:27

You can solve it using bitmask DP.

rohit1507: 2017-09-16 13:49:46

A good question. Feel free to think as you wish. Dont stick to whats mentioned in the comments! :-)

t_s_vedha29: 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 :)

rishi_07: 2017-03-16 11:55:56

Very nice question!!

coderaashir: 2017-02-11 10:31:58

I did simple recursion without DP and it didn't TLE! Very un-strict TL :/

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

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