LeetCode 823. Binary Trees With Factors

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

題目大意

給你一個全相異且嚴格大於

$1$ 之整數陣列

$\text{if }\mathrm{\exists }A,B,C\in \text{arr}:C=A\times B$
則將

$A$,

$B$ 作為

$C$ 之 children

求我們可以做多少個這樣的二元樹？
因為數字很大，題目要我們答案再

$\mathrm{mod}{10}^9+7$

思考

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

其實呢，仔細品味題目後應該會有股熟悉的感覺
二元樹，所以每次就是抓兩個數字相乘去比較…唉？這題好像 LeetCode 1. Two Sum
啊😮😮😮
沒錯，所以我們這邊也一樣會用到 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],\mathrm{\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;
    }