1420. Build Array Where You Can Find The Maximum Exactly K Comparisons Hard

1/**
2 * [1420] Build Array Where You Can Find The Maximum Exactly K Comparisons
3 *
4 * You are given three integers n, m and k. Consider the following algorithm to find the maximum element of an array of positive integers:
5 * <img alt="" src="https://assets.leetcode.com/uploads/2020/04/02/e.png" style="width: 424px; height: 372px;" />
6 * You should build the array arr which has the following properties:
7 * 
8 * 	arr has exactly n integers.
9 * 	1 <= arr[i] <= m where (0 <= i < n).
10 * 	After applying the mentioned algorithm to arr, the value search_cost is equal to k.
11 * 
12 * Return the number of ways to build the array arr under the mentioned conditions. As the answer may grow large, the answer must be computed modulo 10^9 + 7.
13 *  
14 * Example 1:
15 * 
16 * Input: n = 2, m = 3, k = 1
17 * Output: 6
18 * Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]
19 * 
20 * Example 2:
21 * 
22 * Input: n = 5, m = 2, k = 3
23 * Output: 0
24 * Explanation: There are no possible arrays that satisify the mentioned conditions.
25 * 
26 * Example 3:
27 * 
28 * Input: n = 9, m = 1, k = 1
29 * Output: 1
30 * Explanation: The only possible array is [1, 1, 1, 1, 1, 1, 1, 1, 1]
31 * 
32 *  
33 * Constraints:
34 * 
35 * 	1 <= n <= 50
36 * 	1 <= m <= 100
37 * 	0 <= k <= n
38 * 
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/
43// discuss: https://leetcode.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn num_of_arrays(n: i32, m: i32, k: i32) -> i32 {
49        0
50    }
51}
52
53// submission codes end
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    #[test]
60    fn test_1420() {
61    }
62}
63