#3193

Count the Number of Inversions

international master · 1995 · lc hard +32 · 29.8% accepted · 183 likes · top 7%

Description

You are given an integer n and a 2D array requirements, where requirements[i] = [endi, cnti] specifies an end index and a required inversion count.

An inversion in an integer array is a pair of indices (i, j) satisfying i < j and nums[i] > nums[j].

Count how many permutations perm of [0, 1, 2, ..., n - 1] satisfy every requirement, meaning perm[0..endi] has exactly cnti inversions for all i.

Return the count modulo 10⁹ + 7.

Code

1

2

3

class Solution:
    def numberOfPermutations(self, n: int, requirements: List[List[int]]) -> int:

class Solution:
    def numberOfPermutations(self, n: int, requirements: List[List[int]]) -> int: