带因子的二叉树 图解题解

非叶结点等于两孩子相乘，这树怎么数

给一个数组 arr，元素互不相同、都大于 1。拿这些数当结点搭二叉树，同一个数可反复用，规矩是每个非叶结点必须正好等于左孩子乘右孩子。问能搭出多少种不同的树，对 1e9+7（一个常用大质数）取余。

拿题面的 arr = [2, 4, 5, 10]，答案是 7：四个数各自单独成一棵只有根的树是 4 棵，再加 4 = 2×2、10 = 2×5、10 = 5×2 三棵有孩子的凑够 7（左 2 右 5 与左 5 右 2 算两棵）。

为什么不能把所有树形硬枚举一遍

一个数当根、两个孩子又各能往下长子树，形状随规模成倍翻，把每种树都摆出来一棵棵数根本数不完；而且同一棵子树在很多处被从头重算。既然「以某数为根能搭几棵树」能独立回答又反复用到，算一次存下来就行，就是动态规划那套。

为什么先排序，dp[v] 定成什么

先把 arr 从小到大排序。定义 dp[v] 为「以 v 为根能搭多少棵合法树」。v 当非叶根就得拆成两因子 a×b = v 当左右孩子，而 a、b 都大于 1，都严格小于 v。

a、b 都比 v 小，排完一定排在 v 左边，算 dp[v] 时它们的 dp 早已就绪；不排序会取到没累加完的半成品。

dp[a]×dp[b] 为什么是相乘不是相加

dp[v] 从 1 起步——单个数本身就是一棵只有根的合法树。再枚举每对满足 a×b = v 且 a、b 都在 arr 里的因子，把 dp[a]×dp[b] 累加进去。这里用乘法原理（两件事各自独立选，总方案是各自方案数相乘）：左孩子有 dp[a] 种长法、右孩子有 dp[b] 种，各挑各的互不牵制，组合就是 dp[a]×dp[b] 种。

枚举只需扫一个因子 a，商 c = v÷a 若在 arr 里就配一对。累加是相乘不是相加，最易写反。

拿 [2,4,5,10] 把四个 dp 逐格填出来

排序后是 2, 4, 5, 10，dp 全从 1 起步。dp[2]：前面无更小的数，保持 1。dp[4]：先记单点 1 棵，试 2，4÷2 = 2 在表里，累加 dp[2]×dp[2] = 1，得 2。

dp[5]：试 2、试 4 都除不尽，锁定 1。dp[10]：先记单点 1 棵；试 2，10÷2 = 5 在表里，累加 dp[2]×dp[5] = 1，变 2；试 5，10÷5 = 2 在表里，累加 dp[5]×dp[2] = 1，变 3。四格是 1、2、1、3，答案 1+2+1+3 = 7，与题面对上。

dp[a]×dp[b] 不取余为什么会溢出成负数

外层枚举根、内层枚举较小因子，两层都是 n；配「值到下标」哈希表（一种能瞬间查『某个数在不在』的表）让「商在不在数组」做到 O(1)，整体 O(n²)，空间 O(n)。arr 全是质数或两两互质（任意两个数没有大于 1 的公因子）时，谁都拆不出表里的因子，答案就等于元素个数。

累加时 dp[a]×dp[b] 会撑爆整型，每加不立刻对 1e9+7 取余就溢出翻成负数、答案全错；a≠c 那对左右不对称，「左 a 右 c」和「左 c 右 a」是两棵不同的树，内层扫到 a 和扫到 c 各计一次，少数一遍就漏掉一半组合。

Python

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

C++

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

Java

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