题目描述

给出一个含有不重复整数元素的数组，每个整数均大于 1。

我们用这些整数来构建二叉树，每个整数可以使用任意次数。

其中：每个非叶结点的值应等于它的两个子结点的值的乘积。

满足条件的二叉树一共有多少个？返回的结果应 模 10 ^ 9 + 7。

样例

输入: A = [2, 4]
输出: 3
解释: 我们可以得到这些二叉树: [2], [4], [4, 2, 2]。

输入: A = [2, 4, 5, 10]
输出: 7
解释: 我们可以得到这些二叉树: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2]。

提示

1. 1 <= A.length <= 1000.
2. 2 <= A[i] <= 10 ^ 9.

算法

(动态规划) $O(n^2)$

1. 将数组从小到大排序。这里的二叉树要求满二叉树（每个结点要求有两个儿子结点）。
2. 设 $f(i)$ 表示以 $A[i]$ 为根，满足条件的二叉树一共有多少个。
3. 对于每一个 $i$，设置 $f(i) = 1$，表示单根的二叉树，然后枚举 $j < i$ 满足 $A[i] % A[j] == 0$，并且 $A[i] / A[j]$ 在数组里出现过，则 $f(i) = f(i) + f(j) * f(loc(A[i] / A[j]))$，$loc(x)$ 表示查询 $x$ 的下标。这个公式的意思是，将 $A[j]$ 和 $A[i] / A[j]$ 这两个数字分别作为左右子树。
4. 最终答案为 $\sum_{i = 0}^{n - 1}{f(i)}$。

时间复杂度

• 排序需要 $O(n \log n)$ 的时间。
• 动态规划的状态数为 $O(n)$，每次寻找转移需要 $O(n)$ 的时间，故时间复杂度为 $O(n^2)$。

空间复杂度

• 需要额外的数组和哈希表，空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int numFactoredBinaryTrees(vector<int>& A) {
        const int mod = 1000000007;
        int n = A.size();
        sort(A.begin(), A.end());

        unordered_map<int, int> hash;
        for (int i = 0; i < n; i++)
            hash[A[i]] = i;

        vector<int> f(n);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = 0; j < i; j++)
                if (A[i] % A[j] == 0 && hash.find(A[i] / A[j]) != hash.end()) {
                    int k = hash[A[i] / A[j]];
                    f[i] = (f[i] + (long long)(f[j]) * f[k]) % mod;
                }
            ans = (ans + f[i]) % mod;
        }
        return ans;
    }
};