3405. Count the Number of Arrays with K Matching Adjacent Elements Hard

1/**
2 * [3405] Count the Number of Arrays with K Matching Adjacent Elements
3 *
4 * You are given three integers n, m, k. A good array arr of size n is defined as follows:
5 * 
6 * 	Each element in arr is in the inclusive range [1, m].
7 * 	Exactly k indices i (where 1 <= i < n) satisfy the condition arr[i - 1] == arr[i].
8 * 
9 * Return the number of good arrays that can be formed.
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, m = 2, k = 1</span>
15 * Output: <span class="example-io">4</span>
16 * Explanation:
17 * 
18 * 	There are 4 good arrays. They are [1, 1, 2], [1, 2, 2], [2, 1, 1] and [2, 2, 1].
19 * 	Hence, the answer is 4.
20 * </div>
21 * <strong class="example">Example 2:
22 * <div class="example-block">
23 * Input: <span class="example-io">n = 4, m = 2, k = 2</span>
24 * Output: <span class="example-io">6</span>
25 * Explanation:
26 * 
27 * 	The good arrays are [1, 1, 1, 2], [1, 1, 2, 2], [1, 2, 2, 2], [2, 1, 1, 1], [2, 2, 1, 1] and [2, 2, 2, 1].
28 * 	Hence, the answer is 6.
29 * </div>
30 * <strong class="example">Example 3:
31 * <div class="example-block">
32 * Input: <span class="example-io">n = 5, m = 2, k = 0</span>
33 * Output: <span class="example-io">2</span>
34 * Explanation:
35 * 
36 * 	The good arrays are [1, 2, 1, 2, 1] and [2, 1, 2, 1, 2]. Hence, the answer is 2.
37 * </div>
38 *  
39 * Constraints:
40 * 
41 * 	1 <= n <= 10^5
42 * 	1 <= m <= 10^5
43 * 	0 <= k <= n - 1
44 * 
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/count-the-number-of-arrays-with-k-matching-adjacent-elements/
49// discuss: https://leetcode.com/problems/count-the-number-of-arrays-with-k-matching-adjacent-elements/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53impl Solution {
54    pub fn count_good_arrays(n: i32, m: i32, k: i32) -> i32 {
55        0
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_3405() {
67    }
68}
69