C ++中具有因子的二叉树
假设我们有一个正整数列表；其值大于1。我们将使用这些整数创建一棵二叉树，每个数字可以根据需要使用多次。每个非叶节点应为其子节点的乘积。所以我们必须找到多少棵树？答案将以模10^9+7返回。因此，如果输入像[2,4,5,10]，那么答案将是7，因为我们可以制作7棵树，例如[2]，[4]，[5]，[10]，[4,2,2]，[10,2,5]，[10,5,2]
为了解决这个问题，我们将遵循以下步骤-
定义映射dp
对数组A进行排序，n：=数组A的大小，ret：=0
对于i，范围为0至n–1
如果A[i]modA[j]=0，则
dp[A[i]]：=dp[A[i]]+（dp[A[j]]*dp[A[i]]/dp[A[j]]）
使dp[A[i]]增加1
对于介于0到j–1的j
ret：=ret+dp[A[i]]
返回ret
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int 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();
int 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;
}
};
main(){
vector<int> v1 = {2,4,5,10};
Solution ob;
cout << (ob.numFactoredBinaryTrees(v1));
}输入值
[2,4,5,10]
输出结果
7