rustgym/leetcode/
_823_binary_trees_with_factors.rs

1struct Solution;
2use std::collections::HashMap;
3
4impl Solution {
5    fn num_factored_binary_trees(mut a: Vec<i32>) -> i32 {
6        let n = a.len();
7        let mut dp: Vec<i64> = vec![1; n];
8        let modulo = 1_000_000_007;
9        let mut hm: HashMap<i32, usize> = HashMap::new();
10        a.sort_unstable();
11        let mut res = 0;
12        for i in 0..n {
13            hm.insert(a[i], i);
14            for j in 0..i {
15                if a[i] % a[j] == 0 {
16                    if let Some(&k) = hm.get(&(a[i] / a[j])) {
17                        dp[i] += dp[j] * dp[k];
18                    }
19                }
20            }
21            res = (res + dp[i]) % modulo;
22        }
23        res as i32
24    }
25}
26
27#[test]
28fn test() {
29    let a = vec![2, 4];
30    let res = 3;
31    assert_eq!(Solution::num_factored_binary_trees(a), res);
32    let a = vec![2, 4, 5, 10];
33    let res = 7;
34    assert_eq!(Solution::num_factored_binary_trees(a), res);
35}