带因子的二叉树 图解题解

这道题到底在问什么

输入

arr = [2, 4, 5, 10]

输出

7

先想最直接的笨办法

记住这句口诀：排序、dp 从 1 起步、枚举因子对、乘法原理累加、最后求和。后面每一帧都在套它。（动画第 3 步）

最优解：一步一步想明白

1. 3记住这句口诀：排序、dp 从 1 起步、枚举因子对、乘法原理累加、最后求和。后面每一帧都在套它。
2. 4第一步先排序：2, 4, 5, 10。排序是为了保证算到 x 时，比它小的因子都已经算好 dp 了。右边面板就是 dp 表，现在每个值都是 1。
3. 5dp[x] 为什么从 1 起步？因为任何一个数单独拎出来就是一棵只有根的合法树。这 4 个 1，就是示例 7 棵里最朴素的 4 棵。
4. 6强调一下顺序：因子 b、c 都严格小于它们的乘积 x，排序后它们一定排在 x 前面、dp 已经算好。所以从左往右一个个算，永远能拿到现成的因子 dp。
5. 7先看最小的 2。它要拆成两个因子相乘，最小也得是别的数当孩子，但没有比它更小的数在表里，所以 2 只能是单结点，dp[2] 保持 1。
6. 8轮到 4。先把它自己当单结点那 1 棵记上，dp[4] 从 1 起步。接着去前面找：有没有两个数相乘正好等于 4，能当它的左右孩子。
7. 9试因子 2：4 能被 2 整除，商是 2，而 2 也在表里。这就凑成一对合法孩子，左孩子 2、右孩子 2 相乘正好 4。
8. 10用乘法原理：左子树有 dp[2] = 1 种长法，右子树有 dp[2] = 1 种，自由组合就是 1 × 1 = 1 种，累加进 dp[4]，现在是 2。
9. 114 的因子对枚举完了，dp[4] 最终是 2：单结点 1 棵，加上各因子对带来的组合。
10. 12轮到 5。先把它自己当单结点那 1 棵记上，dp[5] 从 1 起步。接着去前面找：有没有两个数相乘正好等于 5，能当它的左右孩子。
11. 13试因子 2：5 除以 2 除不尽，2 根本不是 5 的因子，当不了它的孩子，跳过。
12. 14试因子 4：5 除以 4 除不尽，4 根本不是 5 的因子，当不了它的孩子，跳过。
13. 155 前面的数都没法两两相乘等于它，所以它只有单结点这一种，dp[5] 锁定为 1。
14. 16轮到 10。先把它自己当单结点那 1 棵记上，dp[10] 从 1 起步。接着去前面找：有没有两个数相乘正好等于 10，能当它的左右孩子。
15. 17试因子 2：10 能被 2 整除，商是 5，而 5 也在表里。这就凑成一对合法孩子，左孩子 2、右孩子 5 相乘正好 10。
16. 18用乘法原理：左子树有 dp[2] = 1 种长法，右子树有 dp[5] = 1 种，自由组合就是 1 × 1 = 1 种，累加进 dp[10]，现在是 2。
17. 19试因子 4：10 除以 4 除不尽，4 根本不是 10 的因子，当不了它的孩子，跳过。
18. 20试因子 5：10 能被 5 整除，商是 2，而 2 也在表里。这就凑成一对合法孩子，左孩子 5、右孩子 2 相乘正好 10。
19. 21用乘法原理：左子树有 dp[5] = 1 种长法，右子树有 dp[2] = 1 种，自由组合就是 1 × 1 = 1 种，累加进 dp[10]，现在是 3。
20. 2210 的因子对枚举完了，dp[10] 最终是 3：单结点 1 棵，加上各因子对带来的组合。
21. 23四个 dp 都算好了：2 是 1 棵，4 是 2 棵，5 是 1 棵，10 是 3 棵。每个数当根能搭多少树，面板里一目了然。
22. 24每个数都可以当整棵树的根，所以答案是把所有 dp 加起来：1 + 2 + 1 + 3 = 7。
23. 25于是 arr = [2, 4, 5, 10] 一共能搭出 7 棵合法二叉树，和示例对上了。数据大时记得每步对 1e9+7 取余。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        mod = 10**9 + 7
        n = len(arr)
        arr.sort()
        idx = {v: i for i, v in enumerate(arr)}
        f = [1] * n
        for i, a in enumerate(arr):
            for j in range(i):
                b = arr[j]
                if a % b == 0 and (c := (a // b)) in idx:
                    f[i] = (f[i] + f[j] * f[idx[c]]) % mod
        return sum(f) % mod

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int numFactoredBinaryTrees(vector<int>& arr) {
        const int mod = 1e9 + 7;
        sort(arr.begin(), arr.end());
        unordered_map<int, int> idx;
        int n = arr.size();
        for (int i = 0; i < n; ++i) {
            idx[arr[i]] = i;
        }
        vector<long> f(n, 1);
        for (int i = 0; i < n; ++i) {
            int a = arr[i];
            for (int j = 0; j < i; ++j) {
                int b = arr[j];
                if (a % b == 0) {
                    int c = a / b;
                    if (idx.count(c)) {
                        int k = idx[c];
                        f[i] = (f[i] + 1l * f[j] * f[k]) % mod;
                    }
                }
            }
        }
        long ans = 0;
        for (long v : f) {
            ans = (ans + v) % mod;
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int numFactoredBinaryTrees(int[] arr) {
        final int mod = (int) 1e9 + 7;
        Arrays.sort(arr);
        int n = arr.length;
        long[] f = new long[n];
        Arrays.fill(f, 1);
        Map<Integer, Integer> idx = new HashMap<>(n);
        for (int i = 0; i < n; ++i) {
            idx.put(arr[i], i);
        }
        for (int i = 0; i < n; ++i) {
            int a = arr[i];
            for (int j = 0; j < i; ++j) {
                int b = arr[j];
                if (a % b == 0) {
                    int c = a / b;
                    if (idx.containsKey(c)) {
                        int k = idx.get(c);
                        f[i] = (f[i] + f[j] * f[k]) % mod;
                    }
                }
            }
        }
        long ans = 0;
        for (long v : f) {
            ans = (ans + v) % mod;
        }
        return (int) ans;
    }
}

复杂度

面试官可能追问