Description
For an integer array nums, an inverse pair is a pair of indices (i, j) where i < j and nums[i] > nums[j]. Given two integers n and k, return the number of different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs.
Examples
Input:
n = 3, k = 0Output:
1Explanation:
Only [1,2,3] has 0 inverse pairs.
Input:
n = 4, k = 2Output:
5Explanation:
For n=4, arrays with exactly 2 inverse pairs are needed. Valid arrays: [1,3,2,4] with pairs (3,2), [2,1,3,4] with pairs (2,1), [1,2,4,3] with pairs (4,3), [3,1,2,4] with pairs (3,1) and (3,2) - that has 2 pairs. There are 5 such arrays total.
Input:
n = 2, k = 1Output:
1Explanation:
For n=2, only [2,1] has exactly 1 inverse pair (2 before 1). The array [1,2] has 0 inverse pairs. So the count is 1.
Constraints
- •
1 ≤ n ≤ 1000 - •
0 ≤ k ≤ 1000