3193. Count the Number of Inversions Hard

1/**
2 * [3193] Count the Number of Inversions
3 *
4 * 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.
5 * A pair of indices (i, j) from an integer array nums is called an inversion if:
6 * 
7 * 	i < j and nums[i] > nums[j]
8 * 
9 * Return the number of <span data-keyword="permutation">permutations</span> perm of [0, 1, 2, ..., n - 1] such that for all requirements[i], perm[0..endi] has exactly cnti inversions.
10 * Since the answer may be very large, return it modulo 10^9 + 7.
11 *  
12 * <strong class="example">Example 1:
13 * <div class="example-block">
14 * Input: <span class="example-io">n = 3, requirements = [[2,2],[0,0]]</span>
15 * Output: <span class="example-io">2</span>
16 * Explanation:
17 * The two permutations are:
18 * 
19 * 	[2, 0, 1]
20 * 	
21 * 		Prefix [2, 0, 1] has inversions (0, 1) and (0, 2).
22 * 		Prefix [2] has 0 inversions.
23 * 	
24 * 	
25 * 	[1, 2, 0]
26 * 	
27 * 		Prefix [1, 2, 0] has inversions (0, 2) and (1, 2).
28 * 		Prefix [1] has 0 inversions.
29 * 	
30 * 	
31 * </div>
32 * <strong class="example">Example 2:
33 * <div class="example-block">
34 * Input: <span class="example-io">n = 3, requirements = [[2,2],[1,1],[0,0]]</span>
35 * Output: 1
36 * Explanation:
37 * The only satisfying permutation is [2, 0, 1]:
38 * 
39 * 	Prefix [2, 0, 1] has inversions (0, 1) and (0, 2).
40 * 	Prefix [2, 0] has an inversion (0, 1).
41 * 	Prefix [2] has 0 inversions.
42 * </div>
43 * <strong class="example">Example 3:
44 * <div class="example-block">
45 * Input: <span class="example-io">n = 2, requirements = [[0,0],[1,0]]</span>
46 * Output: <span class="example-io">1</span>
47 * Explanation:
48 * The only satisfying permutation is [0, 1]:
49 * 
50 * 	Prefix [0] has 0 inversions.
51 * 	Prefix [0, 1] has an inversion (0, 1).
52 * </div>
53 *  
54 * Constraints:
55 * 
56 * 	2 <= n <= 300
57 * 	1 <= requirements.length <= n
58 * 	requirements[i] = [endi, cnti]
59 * 	0 <= endi <= n - 1
60 * 	0 <= cnti <= 400
61 * 	The input is generated such that there is at least one i such that endi == n - 1.
62 * 	The input is generated such that all endi are unique.
63 * 
64 */
65pub struct Solution {}
66
67// problem: https://leetcode.com/problems/count-the-number-of-inversions/
68// discuss: https://leetcode.com/problems/count-the-number-of-inversions/discuss/?currentPage=1&orderBy=most_votes&query=
69
70// submission codes start here
71
72impl Solution {
73    pub fn number_of_permutations(n: i32, requirements: Vec<Vec<i32>>) -> i32 {
74        0
75    }
76}
77
78// submission codes end
79
80#[cfg(test)]
81mod tests {
82    use super::*;
83
84    #[test]
85    fn test_3193() {
86    }
87}
88