# LeetCode 823. Binary Trees With Factors

https://leetcode.com/problems/binary-trees-with-factors/description/

## 題目大意

給你一個**全相異**且嚴格大於 $1$ 之整數陣列
$\text{if } \exists A,B,C\in \text{arr} : C = A\times B$
則將 $A$, $B$ 作為 $C$ 之 children

求我們可以做多少個這樣的**二元樹**？
因為數字很大，題目要我們答案再$\mod 10^9+7$

## 思考

題目講的是 binary tree，不是 binary search tree，要看仔細
所以左右子樹可以對調，算做不同的 tree

其實呢，仔細品味題目後應該會有股熟悉的感覺
二元樹，所以每次就是抓兩個數字相乘去比較...唉？這題好像 [LeetCode 1. Two Sum
](https://hackmd.io/@RyoukiWei/leetcode1) 啊😮😮😮
沒錯，所以我們這邊也一樣會用到 `unordered_map` 協助找另一個數字

另外，這題其實還用到了 DP


對於以 $C$ 為 `root` 之 binary tree，其可能之組合即：

1. 僅自身一點
2. $A$ 與 $B$ 各自可能之排列組合

每個 `arr` 中的元素都可以自成一顆 binary tree
所以我們 `dp` 初始值設 `1`

並且我們知道關係式可以寫成

$$
\text{dp} [C] = 1+\sum \text{dp} [a]\cdot \text{dp} [b], \forall a\in A, b\in B
$$

class Solution
{
public:
    int numFactoredBinaryTrees(vector<int> &arr)
    {
        const long MODULO = 1e9 + 7;
        unordered_map<int, long> dp;
        sort(arr.begin(), arr.end());

        for (int i = 0; i < arr.size(); i++)
        {
            dp[arr[i]] = 1;

            for (int j = 0; j < i; j++)
            {
                int temp = arr[i] / arr[j];
                if (!(arr[i] % arr[j]) && dp.count(temp))
                    dp[arr[i]] += (dp[arr[j]] * dp[temp]) % MODULO;
            }
        }

        long ans = 0;
        for (const auto &kv : dp)
        {
            ans += kv.second;
        }

        return ans % MODULO;
    }