难度: Medium
给出一个含有不重复整数元素的数组 arr ，每个整数 arr[i] 均大于 1。
用这些整数来构建二叉树，每个整数可以使用任意次数。其中：每个非叶结点的值应等于它的两个子结点的值的乘积。
满足条件的二叉树一共有多少个？答案可能很大，返回 对 109 + 7 取余 的结果。
示例 1:
输入:arr = [2, 4]输出: 3 解释: 可以得到这些二叉树:[2], [4], [4, 2, 2]
示例 2:
输入:arr = [2, 4, 5, 10]输出:7解释: 可以得到这些二叉树:[2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].
提示：
1 <= arr.length <= 10002 <= arr[i] <= 109arr 中的所有值 互不相同运行时间: 58 ms
内存: 17.5 MB
class Solution:
def numFactoredBinaryTrees(self, arr: List[int]) -> int:
arr.sort()
l = len(arr)
d = {}
for i in arr:d[i] = []
for i in range(l):
if arr[i]**2 > arr[-1]:break
for j in range(i,l):
s = arr[i] * arr[j]
if s in d:d[s].append([arr[i],arr[j]])
elif s > arr[-1]:break
@cache
def f(x):
if not d[x]:return 1
res = 1
for i,j in d[x]:
res += f(i) * f(j) * (2 if i != j else 1)
return res%1000000007
res = 0
for i in arr:res += f(i)
return res%1000000007
这个题解的思路是首先对输入数组进行排序，然后用哈希表记录每个数的因子对。接着使用记忆化搜索，对于每个数，如果它没有因子对，则只有它自己这一种情况；如果有因子对，则结果是它的每个因子对的情况数相乘再相加。最后对每个数的情况数求和并取模即可。
时间复杂度: O(n^2)
空间复杂度: O(n^2)
class Solution:
def numFactoredBinaryTrees(self, arr: List[int]) -> int:
arr.sort() # 对输入数组排序
l = len(arr)
d = {} # 哈希表，用于存储每个数的因子对
for i in arr:
d[i] = []
for i in range(l):
if arr[i]**2 > arr[-1]: # 优化：如果当前数的平方已经大于最大数，就没必要继续了
break
for j in range(i,l):
s = arr[i] * arr[j]
if s in d: # 如果乘积在数组中，则加入哈希表
d[s].append([arr[i],arr[j]])
elif s > arr[-1]: # 优化：如果乘积已经大于最大数，就没必要继续了
break
@cache # 记忆化搜索
def f(x):
if not d[x]: # 如果没有因子对，则只有自己这一种情况
return 1
res = 1
for i,j in d[x]: # 遍历所有因子对
res += f(i) * f(j) * (2 if i != j else 1) # 乘以因子对的情况数，如果两个因子相同，则不用乘2
return res % 1000000007
res = 0
for i in arr: # 对每个数的情况数求和
res += f(i)
return res % 1000000007 # 取模
在题解中对输入数组进行排序的原因是为了简化因子对的查找过程。排序后，数组中的每个元素都按照从小到大的顺序排列，这样在遍历数组以构建因子对的哈希表时，可以更有效地确定哪些数可以组成因子对。此外，排序还允许使用二分查找来加速查找过程，虽然在这个具体的题解中没有直接使用二分查找，但排序本身对于确定因子对的上界和下界是有帮助的。例如，如果已知一个数的平方已经大于数组中的最大数，则可以直接停止内层循环，避免不必要的计算。
这个优化的逻辑基于一个事实：如果某个数的平方已经大于数组中的最大数，那么这个数与数组中任何数的乘积也必然大于数组中的最大数。因此，当发现当前数的平方超过了数组中的最大数时，就可以停止考虑以这个数作为因子对中一个因子的可能性，从而跳出循环。这种优化减少了不必要的迭代和计算，提高了整体算法的效率，尤其是在数组中包含较大数值时更为明显。
使用`@cache`进行记忆化搜索可以大幅提升性能，主要是通过避免重复计算已经计算过的结果。在这个问题中，每个数的因子对可能会在求解其他数的因子对情况时被重复计算多次。通过记忆化搜索，一旦某个数的所有因子对的情况数被计算过，就会存储起来，后续的搜索可以直接使用存储的结果，无需再次进行复杂的计算。这样大大减少了计算量，尤其是在面对较大的输入数组时，能有效避免算法的时间复杂度指数级增加。
基于的考虑是效率和计算的精确性。当发现某个因子对的乘积超过数组中的最大数时，这个乘积不可能作为有效的因子对出现在任何结果中，因为数组中不存在这样的数。因此，继续计算这种情况下的乘积是不必要的，直接跳出循环可以节省计算资源。这种做法不会遗漏有效的因子对，因为所有有效的因子对的乘积必须是数组中已存在的数。