3193. Count the Number of Inversions

Problem Link

Description

---

You are given an integer n and a 2D array requirements, where requirements[i] = [endi, cnti] represents the end index and the inversion count of each requirement.

A pair of indices (i, j) from an integer array nums is called an inversion if:

• i < j and nums[i] > nums[j]

Return the number of permutations perm of [0, 1, 2, ..., n - 1] such that for all requirements[i], perm[0..endi] has exactly cnti inversions.

Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: n = 3, requirements = [[2,2],[0,0]]

Output: 2

Explanation:

The two permutations are:

• [2, 0, 1]

  <ul>
  	<li>Prefix <code>[2, 0, 1]</code> has inversions <code>(0, 1)</code> and <code>(0, 2)</code>.</li>
  	<li>Prefix <code>[2]</code> has 0 inversions.</li>
  </ul>
  </li>
  <li><code>[1, 2, 0]</code>
  <ul>
  	<li>Prefix <code>[1, 2, 0]</code> has inversions <code>(0, 2)</code> and <code>(1, 2)</code>.</li>
  	<li>Prefix <code>[1]</code> has 0 inversions.</li>
  </ul>
  </li>
  

Example 2:

Input: n = 3, requirements = [[2,2],[1,1],[0,0]]

Output: 1

Explanation:

The only satisfying permutation is [2, 0, 1]:

• Prefix [2, 0, 1] has inversions (0, 1) and (0, 2).
• Prefix [2, 0] has an inversion (0, 1).
• Prefix [2] has 0 inversions.

Example 3:

Input: n = 2, requirements = [[0,0],[1,0]]

Output: 1

Explanation:

The only satisfying permutation is [0, 1]:

• Prefix [0] has 0 inversions.
• Prefix [0, 1] has an inversion (0, 1).

 

Constraints:

• 2 <= n <= 300
• 1 <= requirements.length <= n
• requirements[i] = [endi, cnti]
• 0 <= endi <= n - 1
• 0 <= cnti <= 400
• The input is generated such that there is at least one i such that endi == n - 1.
• The input is generated such that all endi are unique.

Solution

---

Python3

class Solution:
    def numberOfPermutations(self, n: int, requirements: List[List[int]]) -> int:
        MOD = 10 ** 9 + 7
        have = [-1] * n
 
        for end, cnt in requirements:
            have[end] = cnt
 
        @cache
        def go(index, left):
            if index == 0: return int(left == 0)
 
            res = 0
 
            if have[index] == -1 or have[index] == left:
                for k in range(min(index, left) + 1):
                    res += go(index - 1, left - k)
                    res %= MOD
 
            return res
 
        return go(n - 1, have[n - 1])