: https://leetcode.com/problems/binary-trees-with-factors/description/
: 823. Binary Trees With Factors
: 给你一个阵列 arr，里面的数字不重复且大于 1，我们可以不限制次数的使用这些
: 数字构建出一个二元树，这个二元树需要满足左右节点的值相乘等于父节点，求出
: 共有几种组合。
: Example 1:
: Input: arr = [2,4]
: Output: 3
: Explanation: We can make these trees: [2], [4], [4, 2, 2]
思路：题目可以解读成从arr中找到一个数 恰等于 两个数相乘，
且自己一个数也算一种组合
1.也是想到动态规划
如果 i = j*k 且 (i,j,k) 都在arr里面
则 [sum == i的组合] 就多了 [sum == j的组合] * [sum == k的组合]
2.没有重复的数字，不用考虑重复答案的删除
3.数字都>1，不用考虑1*自己的case
comb[i] :定义为 sum = i的总组合数
从 i = arr.min() 依序算到 i = arr.max()就可以了
[作法1] comb = [0] * (max(arr)+1)
// 结果MLE
[作法2] 利用map存需要的comb[i]
========== Python
class Solution:
def numFactoredBinaryTrees(self, arr: List[int]) -> int:
comb = {}
for i in range(len(arr)):
comb[arr[i]] = 1
for num in sorted(comb.keys()):
for j in range(len(arr)):
if (num <= arr[j]):
continue
elif (num > arr[j] and num % arr[j] == 0 and (num//arr[j] in
comb)):
comb[num] += comb[arr[j]] * comb[num//arr[j]]
summary = 0
for num, count in comb.items():
summary += count
return summary % (10**9+7)
========== C++
C++不像Python，int会爆炸，这边用long long
==========
class Solution {
public:
int numFactoredBinaryTrees(vector<int>& arr) {
# define ll long long
const int MOD = 1e9+7;
map<ll, ll> mp;
for (const auto& num : arr)
{
mp[num] = 1;
}
for (const auto& [num, count] : mp)
{
for (const ll& anum : arr)
{
if (num <= anum){}
else if ((num > anum) && (num % anum == 0) &&
(mp.count(num/anum) == 1))
{
mp[num] += (mp[anum] * mp[num/anum]);
}
}
}
ll sum = 0;
for (const auto& [num, count] : mp)
{
sum += count;
}
return sum % MOD;
}
};