#629

K Inverse Pairs Array

candidate master · 1460 · lc hard +32 · verified · 49% accepted · 2,777 likes · top 35%

Description

An inverse pair in an array is a pair of indices (i, j) with i < j and nums[i] > nums[j]. Given integers n and k, count all permutations of [1..n] that contain exactly k inverse pairs. Return the count modulo 10⁹ + 7.

Example 1:

Input: n = 3, k = 0

Output: 1

Explanation: Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pairs.

Example 2:

Input: n = 3, k = 1

Output: 2

Explanation: The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.

Code

1

2

3

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:

class Solution:
    def kInversePairs(self, n: int, k: int) -> int: