[Rust] Trie solution O(N^2), beats 100%
Complexity
Time complexity: O(N2)
Code
# Complexity
- Time complexity: $$O(N^2)$$

# Code
```rust []
use std::collections::HashMap;

struct Trie {
    pub children: HashMap<i32, Trie>,
}
impl Trie {
    pub fn new() -> Self {
        Self { children: HashMap::new() }
    }
}

impl Solution {
    pub fn count_distinct(nums: Vec<i32>, k: i32, p: i32) -> i32 {
        let (mut ans, mut root, n) = (0, Trie::new(), nums.len());
        for i in 0..n {
            let (mut cur, mut divs) = (&mut root, 0);
            for j in i..n {
                if nums[j]%p==0 { divs+=1; }
                if divs > k { break; }

                if !cur.children.contains_key(&nums[j]) {
                    cur.children.insert(nums[j], Trie::new());
                    ans+=1;
                }
                cur = cur.children.get_mut(&nums[j]).unwrap();
            }
        }
        ans
    }
}
```

![image.png](https://assets.leetcode.com/users/images/2e562a9e-f126-4dae-a432-d0a9ec22573f_1734982407.1659777.png)

['Hash Table', 'Trie', 'Rust']