C++の要素を持つ二分木

正の整数のリストがあるとします。その値は1より大きいです。これらの整数を使用して二分木を作成します。各数値は何度でも使用できます。各非リーフノードは、その子の生成物である必要があります。それで、私たちは何本の木を作ることができるかを見つけなければなりませんか？答えはモジュロ10^9 + 7で返されます。したがって、入力が[2,4,5,10]の場合、[2]、[4]のように7つのツリーを作成できるため、答えは7になります。 、[5]、[10]、[4,2,2]、[10,2,5]、[10,5,2]

これを解決するには、次の手順に従います-

• マップdpを定義する
• 配列Aを並べ替える、n：=配列Aのサイズ、ret：=0
• 0からn–1の範囲のiの場合
  • dp[A[i]]を1増やします
  • 0からj–1の範囲のjの場合
    • A [i] mod A [j] =0の場合、
      • dp [A [i]]：=dp [A [i]] +（dp [A [j]] * dp [A [i]] / dp [A [j]]）
  • ret：=ret + dp [A [i]]
• return 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