Orderings With an Exact Inversion Count

Hard

An inversion in an array is a pair of positions i < j where the left element is larger than the right one: a[i] > a[j]. Given size and inversions, count the permutations of the numbers 1 to size that have exactly inversions inversions. The answer can be huge, so return it modulo 10^9 + 7.

Example 1

size=3, inversions=2 → 2

[2, 3, 1] (pairs 2>1 and 3>1) and [3, 1, 2] (pairs 3>1 and 3>2) both qualify.

Example 2

size=4, inversions=6 → 1

Six is the most four numbers can have, and only [4, 3, 2, 1] reaches it.

Example 3

size=5, inversions=3 → 15

Constraints

1 ≤ size ≤ 1000
0 ≤ inversions ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Dynamic Programming

Similar problems

Pattern With Dot and Star Hard Longest Balanced Bracket Stretch Hard Water Between Walls Hard Does the Text Fit the Pattern Hard Biggest Solid Panel Block Hard

Input

size=3, inversions=2

Expected

Run checks the first 3 tests in your browser. Submit checks all 83 tests on the server, hidden ones included.