: 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;
}
};