2338. Count the Number of Ideal Arrays Hard

1/**
2 * [2338] Count the Number of Ideal Arrays
3 *
4 * You are given two integers n and maxValue, which are used to describe an ideal array.
5 * A 0-indexed integer array arr of length n is considered ideal if the following conditions hold:
6 * 
7 * 	Every arr[i] is a value from 1 to maxValue, for 0 <= i < n.
8 * 	Every arr[i] is divisible by arr[i - 1], for 0 < i < n.
9 * 
10 * Return the number of distinct ideal arrays of length n. Since the answer may be very large, return it modulo 10^9 + 7.
11 *  
12 * Example 1:
13 * 
14 * Input: n = 2, maxValue = 5
15 * Output: 10
16 * Explanation: The following are the possible ideal arrays:
17 * - Arrays starting with the value 1 (5 arrays): [1,1], [1,2], [1,3], [1,4], [1,5]
18 * - Arrays starting with the value 2 (2 arrays): [2,2], [2,4]
19 * - Arrays starting with the value 3 (1 array): [3,3]
20 * - Arrays starting with the value 4 (1 array): [4,4]
21 * - Arrays starting with the value 5 (1 array): [5,5]
22 * There are a total of 5 + 2 + 1 + 1 + 1 = 10 distinct ideal arrays.
23 * 
24 * Example 2:
25 * 
26 * Input: n = 5, maxValue = 3
27 * Output: 11
28 * Explanation: The following are the possible ideal arrays:
29 * - Arrays starting with the value 1 (9 arrays): 
30 *    - With no other distinct values (1 array): [1,1,1,1,1] 
31 *    - With 2^nd distinct value 2 (4 arrays): [1,1,1,1,2], [1,1,1,2,2], [1,1,2,2,2], [1,2,2,2,2]
32 *    - With 2^nd distinct value 3 (4 arrays): [1,1,1,1,3], [1,1,1,3,3], [1,1,3,3,3], [1,3,3,3,3]
33 * - Arrays starting with the value 2 (1 array): [2,2,2,2,2]
34 * - Arrays starting with the value 3 (1 array): [3,3,3,3,3]
35 * There are a total of 9 + 1 + 1 = 11 distinct ideal arrays.
36 * 
37 *  
38 * Constraints:
39 * 
40 * 	2 <= n <= 10^4
41 * 	1 <= maxValue <= 10^4
42 * 
43 */
44pub struct Solution {}
45
46// problem: https://leetcode.com/problems/count-the-number-of-ideal-arrays/
47// discuss: https://leetcode.com/problems/count-the-number-of-ideal-arrays/discuss/?currentPage=1&orderBy=most_votes&query=
48
49// submission codes start here
50
51impl Solution {
52    pub fn ideal_arrays(n: i32, max_value: i32) -> i32 {
53        0
54    }
55}
56
57// submission codes end
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    #[test]
64    fn test_2338() {
65    }
66}
67