Count the Number of Inversions
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 < jandnums[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 10^9 + 7.
Example 1
Input
n = 3, requirements = [[2,2],[0,0]]Output
2The two satisfying permutations are
[2, 0, 1] and [1, 2, 0], each having exactly 2 inversions in the full prefix and 0 inversions in the prefix ending at index 0.Example 2
Input
n = 3, requirements = [[2,2],[1,1],[0,0]]Output
1The only satisfying permutation is
[2, 0, 1], whose prefixes ending at indices 2, 1, and 0 have 2, 1, and 0 inversions respectively.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.