3700. Number of ZigZag Arrays II Hard

1/**
2 * [3700] Number of ZigZag Arrays II
3 *
4 * You are given three integers n, l, and r.
5 * A ZigZag array of length n is defined as follows:
6 * 
7 * 	Each element lies in the range [l, r].
8 * 	No two adjacent elements are equal.
9 * 	No three consecutive elements form a strictly increasing or strictly decreasing sequence.
10 * 
11 * Return the total number of valid ZigZag arrays.
12 * Since the answer may be large, return it modulo 10^9 + 7.
13 * A sequence is said to be strictly increasing if each element is strictly greater than its previous one (if exists).
14 * A sequence is said to be strictly decreasing if each element is strictly smaller than its previous one (if exists).
15 *  
16 * <strong class="example">Example 1:
17 * <div class="example-block">
18 * Input: <span class="example-io">n = 3, l = 4, r = 5</span>
19 * Output: <span class="example-io">2</span>
20 * Explanation:
21 * There are only 2 valid ZigZag arrays of length n = 3 using values in the range [4, 5]:
22 * 
23 * 	[4, 5, 4]
24 * 	[5, 4, 5]
25 * </div>
26 * <strong class="example">Example 2:
27 * <div class="example-block">
28 * Input: <span class="example-io">n = 3, l = 1, r = 3</span>
29 * Output: <span class="example-io">10</span>
30 * Explanation:
31 * ​​​​​​​There are 10 valid ZigZag arrays of length n = 3 using values in the range [1, 3]:
32 * 
33 * 	[1, 2, 1], [1, 3, 1], [1, 3, 2]
34 * 	[2, 1, 2], [2, 1, 3], [2, 3, 1], [2, 3, 2]
35 * 	[3, 1, 2], [3, 1, 3], [3, 2, 3]
36 * 
37 * All arrays meet the ZigZag conditions.
38 * </div>
39 *  
40 * Constraints:
41 * 
42 * 	3 <= n <= 10^9
43 * 	1 <= l < r <= 75​​​​​​​
44 * 
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/number-of-zigzag-arrays-ii/
49// discuss: https://leetcode.com/problems/number-of-zigzag-arrays-ii/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53impl Solution {
54    pub fn zig_zag_arrays(n: i32, l: i32, r: 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_3700() {
67    }
68}
69