leetcode [823] 带因子的二叉树

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

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

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

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

示例 1:

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

示例 2:

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

提示:

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

来自题解:

先排序，这样当前元素的所有因子都在当前元素之前。初始化dp为1，如果存在因子，加上因子dp乘积。

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A.sort()
        dp = [1 for i in range(len(A))]
        dic = {a: i for i, a in enumerate(A)}
        for i in range(len(A)):
            for j in range(i):
                if A[i] % A[j] != 0:
                    continue
                res = A[i] // A[j]
                if res in dic:
                    dp[i] += dp[j] * dp[dic[res]]
                    dp[i] %= 10**9+7
        return sum(dp) % (10**9 + 7)