3193. Count the Number of Inversions
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
andnums[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]
- Prefix
[2, 0, 1]
has inversions(0, 1)
and(0, 2)
. - Prefix
[2]
has 0 inversions.
- Prefix
[1, 2, 0]
- Prefix
[1, 2, 0]
has inversions(0, 2)
and(1, 2)
. - Prefix
[1]
has 0 inversions.
- Prefix
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 thatendi == n - 1
. - The input is generated such that all
endi
are unique.
Solutions
Solution 1: Dynamic Programming
We define $f[i][j]$ as the number of permutations of $[0..i]$ with $j$ inversions. Consider the relationship between the number $a_i$ at index $i$ and the previous $i$ numbers. If $a_i$ is smaller than $k$ of the previous numbers, then each of these $k$ numbers forms an inversion pair with $a_i$, contributing to $k$ inversions. Therefore, we can derive the state transition equation:
$$ f[i][j] = \sum_{k=0}^{\min(i, j)} f[i-1][j-k] $$
Since the problem requires the number of inversions in $[0..\textit{end}_i]$ to be $\textit{cnt}_i$, when we calculate for $i = \textit{end}_i$, we only need to compute $f[i][\textit{cnt}_i]$. The rest of $f[i][..]$ will be $0$.
The time complexity is $O(n \times m \times \min(n, m))$, and the space complexity is $O(n \times m)$. Here, $m$ is the maximum number of inversions, and in this problem, $m \le 400$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|