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] mod A [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