Given an array of unique integers, each integer is strictly greater than 1.
We make a binary tree using these integers and each number may be used for any number of times.
Each non-leaf node’s value should be equal to the product of the values of it’s children.
How many binary trees can we make? Return the answer modulo 10 ** 9 + 7.
Example 1:
Input: A = [2, 4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]
Example 2:
Input: A = [2, 4, 5, 10]
Output: 7
Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].
Note:
1 <= A.length <= 1000.
2 <= A[i] <= 10 ^ 9.
Solution
class Solution {
static constexpr int MOD = 1000000007;
static int mul(int x, int y) {
int64_t p = (int64_t)x * y;
return (int)(p % MOD);
}
static int add(int x, int y) {
return (x + y) % MOD;
}
public:
int numFactoredBinaryTrees(vector<int>& A) {
sort(A.begin(), A.end());
/* number of binary tree using this A[i] as root. */
vector<int> v;
v.push_back(1);
for (int i = 1; i < A.size(); ++i) {
int n = 1;
for (int ix = 0, iy = i - 1; ix <= iy;) {
if (mul(A[ix], A[iy]) == A[i]) {
int adder = mul(v[ix], v[iy]);
n = add(n, adder);
if (A[ix] != A[iy]) n = add(n, adder);
}
if ((int64_t)A[ix] * A[iy] <= (int64_t)A[i]) ++ix;
else --iy;
}
v.push_back(n);
}
int sum = 0;
for (int n : v) sum = add(sum, n);
return sum;
}
};