leetcode 823 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 <= A.length <= 1000.
2 <= A[i] <= 10 ^ 9.

分析：
构建一个所有父节点的值等于其子节点的值的乘积的树，问有多少种构建方法，注意数据长度小于1000，说明n^2复杂度是可行的

思路：
比如[2,5,10,20],对于20由2和10组成，10又可以由2和5组成，所以组成20的方法应该是组成2的方法数乘以组成10的方法数

1
2
3
4
5
6
7
8
9
10
11
12

def (A):
    import collections
    A.sort()
    d = collections.Counter(A)

    for i in xrange(len(A)):
        
        for j in xrange(i):
            if A[i] % A[j] == 0 and A[i]/A[j] in d:
                d[A[i]] += d[A[j]] * d[A[i]/A[j]]

    return sum(d.values()) % (10**9+7)