Binary Trees With Factors

Given an array of unique integers, each integer is strictly greater than 1.

We make a binary tree using these integers and each number may be used for any number of times.

Each non-leaf node's value should be equal to the product of the values of it's children.

How many binary trees can we make? Return the answer modulo 10 ** 9 + 7.

Example 1:

Input: A = [2, 4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]

Example 2:

Input: A = [2, 4, 5, 10]
Output: 7
Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

Note:

1. 1 <= A.length <= 1000.

2. 2 <= A[i] <= 10 ^ 9.

/**
 * Sort the list A at first. Scan A from small element to bigger.
 * 
 * DP equation: dp[i] = sum(dp[j] * dp[i / j])
 * res = sum(dp[i]) with i, j, i / j in the list L
 */
public class Solution {
    public int numFactoredBinaryTrees(int[] A) {
        long res = 0L, mod = (long) 1e9 + 7;
        Arrays.sort(A);
        HashMap<Integer, Long> dp = new HashMap<>();
        for (int i = 0; i < A.length; ++i) {
            // When tree only contains A[i] as root and no other node
            dp.put(A[i], 1L);
            // Checking smaller elements only
            for (int j = 0; j < i; ++j)
                if (A[i] % A[j] == 0)
                    dp.put(A[i], (dp.get(A[i]) + dp.get(A[j]) * dp.getOrDefault(A[i] / A[j], 0L)) % mod);
            res = (res + dp.get(A[i])) % mod;
        }
        return (int) res;
    }
}