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