823. Binary Trees With Factors

public class Solution {
    public int NumFactoredBinaryTrees(int[] A) {
        const int MOD = 1_000_000_007;
        Array.Sort(A);
        var dp = new long[A.Length];
        Array.Fill(dp, 1);
        var index = new Dictionary<int, int>();
        
        for (int i = 0; i < A.Length; i++) {
            index[A[i]] = i;
        }
        
        for (int i = 0; i < A.Length; i++) {
            for (int j = 0; j < i; j++) {
                if (A[i] % A[j] == 0) {
                    int right = A[i] / A[j];
                    if (index.ContainsKey(right)) {
                        dp[i] = (dp[i] + dp[j] * dp[index[right]]) % MOD;
                    }
                }
            }
        }
        
        long result = 0;
        foreach (long x in dp) {
            result = (result + x) % MOD;
        }
        return (int)result;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int NumFactoredBinaryTrees(vector<int>& A) {
        const int MOD = 1_000_000_007;
        sort(A.begin(), A.end());
        var dp = new long[A.size()];
        Array.Fill(dp, 1);
        var index = new unordered_map<int, int>();
        
        for (int i = 0; i < A.size(); i++) {
            index[A[i]] = i;
        }
        
        for (int i = 0; i < A.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (A[i] % A[j] == 0) {
                    int right = A[i] / A[j];
                    if (index.count(right)) {
                        dp[i] = (dp[i] + dp[j] * dp[index[right]]) % MOD;
                    }
                }
            }
        }
        
        long result = 0;
        foreach (long x in dp) {
            result = (result + x) % MOD;
        }
        return (int)result;
    }
}

class Solution {
    public int numFactoredBinaryTrees(int[] A) {
        int MOD = 1_000_000_007;
        Arrays.sort(A);
        long[] dp = new long[A.length];
        Arrays.fill(dp, 1);
        Map<Integer, Integer> index = new HashMap<>();
        
        for (int i = 0; i < A.length; i++) {
            index.put(A[i], i);
        }
        
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < i; j++) {
                if (A[i] % A[j] == 0) {
                    int right = A[i] / A[j];
                    if (index.containsKey(right)) {
                        dp[i] = (dp[i] + dp[j] * dp[index.get(right)]) % MOD;
                    }
                }
            }
        }
        
        long result = 0;
        for (long x : dp) {
            result = (result + x) % MOD;
        }
        return (int) result;
    }

var numFactoredBinaryTrees = function(A) {
    const MOD = 1_000_000_007;
    A.sort((a, b) => a - b);
    const dp = new Array(A.length).fill(1);
    const index = new Map();
    
    A.forEach((x, i) => index.set(x, i));
    
    for (let i = 0; i < A.length; i++) {
        for (let j = 0; j < i; j++) {
            if (A[i] % A[j] === 0) {
                let right = A[i] / A[j];
                if (index.has(right)) {
                    dp[i] = (dp[i] + dp[j] * dp[index.get(right)]) % MOD;
                }
            }
        }
    }
    
    return dp.reduce((a, b) =>

class Solution:
    def numFactoredBinaryTrees(self, A):
        MOD = 10 ** 9 + 7
        A.sort()
        dp = [1] * len(A)
        index = {x: i for i, x in enumerate(A)}
        
        for i, x in enumerate(A):
            for j in range(i):
                if x % A[j] == 0:
                    right = x // A[j]
                    if right in index:
                        dp[i] += dp[j] * dp[index[right]]
                        dp[i] %= MOD

func numFactoredBinaryTrees(A []int) int {
    const MOD = 1_000_000_007
    sort.Ints(A)
    dp := make([]int64, len(A))
    for i := range dp {
        dp[i] = 1
    }
    index := make(map[int]int)
    for i, x := range A {
        index[x] = i
    }

    for i, x := range A {
        for j := 0; j < i; j++ {
            if x%A[j] == 0 {
                right := x / A[j]
                if k, ok := index[right]; ok {
                    dp[i] = (dp[i] + dp[j]*dp[k]) % MOD
                }
            }
        }
    }

    result := int64(0)
    for _, x := range dp {
        result = (result + x) % MOD
    }
    return int(result)
}

Algorithm

Пусть dp[i] будет количеством способов иметь корневой узел со значением A[i]. Поскольку в приведенном примере мы всегда имеем x < v и y < v, мы можем вычислить значения dp[i] в порядке возрастания, используя динамическое программирование.

Для некоторого значения корня A[i] попробуем найти кандидатов для дочерних узлов со значениями A[j] и A[i] / A[j] (так, чтобы очевидно A[j] * (A[i] / A[j]) = A[i]). Для быстрой реализации этого нам понадобится индекс, который ищет это значение: если A[k] = A[i] / A[j], тогда index[A[i] / A[j]] = k.

После этого добавим все возможные dp[j] * dp[k] (с j < i, k < i) к нашему ответу dp[i]. В нашей реализации на Java мы тщательно использовали long, чтобы избежать проблем с переполнением.

😎