class Solution:
'''
题目:数组不重复,没排序,可多次使用; 树必须是完全二叉树
先排序数组
dp[i]:表示以i对应数字为根结点的方案数量
dp[i] = 1 + f[a]*f[b] + f[c]*f[d] + f[b]*f[a] + f[d]*f[c]
如果i可以被分解成a,b,c,d,且都在arr里, 可用hashmap辅助判断
Init:
dp[0] = 1, 以idx=0为根结点的方案树只有1个
dp[i] = 1, 避免每次单独计算只考虑根结点的情况
Enumerate the root, check the number before root num
determine if nums[i] = nums[j] * nums[need]
T:O(n2), S: O(n)
'''
def numFactoredBinaryTrees(self, arr: List[int]) -> int:
arr.sort()
record = {}
res, MOD = 0, 10**9 +7
for idx, num in enumerate(arr):
record[num] = idx
n = len(arr)
dp = [1] * n
for i in range(n):
for j in range(i):
if arr[i] % arr[j] == 0 and arr[i] // arr[j] in record:
need = arr[i] // arr[j]
dp[i] += dp[j] * dp[record[need]] % MOD
return sum(dp)% MOD