2318. Number of Distinct Roll Sequences Hard

1/**
2 * [2318] Number of Distinct Roll Sequences
3 *
4 * You are given an integer n. You roll a fair 6-sided dice n times. Determine the total number of distinct sequences of rolls possible such that the following conditions are satisfied:
5 * <ol>
6 * 	The greatest common divisor of any adjacent values in the sequence is equal to 1.
7 * 	There is at least a gap of 2 rolls between equal valued rolls. More formally, if the value of the i^th roll is equal to the value of the j^th roll, then abs(i - j) > 2.
8 * </ol>
9 * Return the total number of distinct sequences possible. Since the answer may be very large, return it modulo 10^9 + 7.
10 * Two sequences are considered distinct if at least one element is different.
11 *  
12 * Example 1:
13 * 
14 * Input: n = 4
15 * Output: 184
16 * Explanation: Some of the possible sequences are (1, 2, 3, 4), (6, 1, 2, 3), (1, 2, 3, 1), etc.
17 * Some invalid sequences are (1, 2, 1, 3), (1, 2, 3, 6).
18 * (1, 2, 1, 3) is invalid since the first and third roll have an equal value and abs(1 - 3) = 2 (i and j are 1-indexed).
19 * (1, 2, 3, 6) is invalid since the greatest common divisor of 3 and 6 = 3.
20 * There are a total of 184 distinct sequences possible, so we return 184.
21 * Example 2:
22 * 
23 * Input: n = 2
24 * Output: 22
25 * Explanation: Some of the possible sequences are (1, 2), (2, 1), (3, 2).
26 * Some invalid sequences are (3, 6), (2, 4) since the greatest common divisor is not equal to 1.
27 * There are a total of 22 distinct sequences possible, so we return 22.
28 * 
29 *  
30 * Constraints:
31 * 
32 * 	1 <= n <= 10^4
33 * 
34 */
35pub struct Solution {}
36
37// problem: https://leetcode.com/problems/number-of-distinct-roll-sequences/
38// discuss: https://leetcode.com/problems/number-of-distinct-roll-sequences/discuss/?currentPage=1&orderBy=most_votes&query=
39
40// submission codes start here
41
42impl Solution {
43    pub fn distinct_sequences(n: i32) -> i32 {
44        0
45    }
46}
47
48// submission codes end
49
50#[cfg(test)]
51mod tests {
52    use super::*;
53
54    #[test]
55    fn test_2318() {
56    }
57}
58