带因子的二叉树

/*
 * 思路：
 * 1. 对数组进行排序，确保在处理每个元素时，其所有可能的子节点都已经处理过。
 * 2. 使用动态规划的方法。dp[i] 表示以 arr[i] 为根节点的二叉树的数量。
 * 3. 使用 Java Stream API 进行处理。
 * 4. 对于每一个元素 arr[i]，检查其所有可能的因子 arr[j] 和 arr[k]，
 *    其中 arr[i] = arr[j] * arr[k] 并且 arr[j] 和 arr[k] 也必须在数组中。
 * 5. 对于每一个符合条件的因子组合，dp[i] += dp[j] * dp[k]。
 * 6. 返回 dp 数组所有元素的和，并对 10^9 + 7 取余。
 */

import java.util.*;
import java.util.stream.*;

public class BinaryTreeCountStream {
    public int numFactoredBinaryTrees(int[] arr) {
        int MOD = 1_000_000_007;
        Arrays.sort(arr);
        long[] dp = new long[arr.length];
        Arrays.fill(dp, 1);
        Map<Integer, Integer> index = IntStream.range(0, arr.length).boxed().collect(Collectors.toMap(i -> arr[i], i -> i));
        IntStream.range(0, arr.length).forEach(i -> {
            IntStream.range(0, i).forEach(j -> {
                if (arr[i] % arr[j] == 0) { // arr[j] is a factor of arr[i]
                    int right = arr[i] / arr[j];
                    if (index.containsKey(right)) {
                        dp[i] = (dp[i] + dp[j] * dp[index.get(right)]) % MOD;
                    }
                }
            });
        });
        long ans = Arrays.stream(dp).sum();
        return (int) (ans % MOD);
    }

    public static void main(String[] args) {
        BinaryTreeCountStream btc = new BinaryTreeCountStream();
        int[] arr = {2, 4, 5, 10};
        System.out.println(btc.numFactoredBinaryTrees(arr)); // Output: 7
    }
}