Cây nhị phân với nhân tử C++ (Binary Trees With Factors)

Cho mảng số nguyên dương > 1. Xây cây nhị phân: nút không phải lá = tích 2 con. Số lần dùng không giới hạn. Đếm số cây khác nhau (mod 10⁹+7).

Ví dụ

Input - [2,4,5,10] Output - 7

Giải thích - 7 cây: [2], [4], [5], [10], [4,2,2], [10,2,5], [10,5,2].

Phương pháp tiếp cận (DP + Hash Map)

• Sắp xếp mảng A
• dp[x] = số cây có gốc giá trị x
• Khởi tạo dp[A[i]] = 1 (cây đơn nút)
• Với mỗi A[i], duyệt A[j] (j < i): nếu A[i] % A[j] == 0 và A[i]/A[j] có trong dp → dp[A[i]] += dp[A[j]] * dp[A[i]/A[j]]
• Tổng kết quả = Σ dp[A[i]]

Ví dụ code C++

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

typedef long long lli;
const int MOD = 1e9 + 7;

int add(lli a, lli b) { return ((a % MOD) + (b % MOD)) % MOD; }
int mul(lli a, lli b) { return ((a % MOD) * (b % MOD)) % MOD; }

class Solution {
public:
    int numFactoredBinaryTrees(vector<int>& A) {
        unordered_map<int, int> dp;
        sort(A.begin(), A.end());
        int n = A.size(), ret = 0;
        for (int i = 0; i < n; i++) {
            dp[A[i]] += 1;
            for (int j = 0; j < i; j++) {
                if (A[i] % A[j] == 0) {
                    dp[A[i]] = add(dp[A[i]], mul(dp[A[j]], dp[A[i] / A[j]]));
                }
            }
            ret = add(ret, dp[A[i]]);
        }
        return ret;
    }
};

int main() {
    vector<int> v1 = {2, 4, 5, 10};
    Solution ob;
    cout << ob.numFactoredBinaryTrees(v1);
    return 0;
}

Kết quả

7