C++에서 인수가 있는 이진 트리

<시간/>

양의 정수 목록이 있다고 가정합니다. 이 정수를 사용하여 이진 트리를 만들고 각 숫자를 원하는 만큼 사용할 수 있습니다. 리프가 아닌 각 노드는 하위 노드의 제품이어야 합니다. 그래서 우리는 얼마나 많은 나무를 만들 수 있는지 찾아야 합니까? 답은 모듈로 10^9 + 7로 반환됩니다. 따라서 입력이 [2,4,5,10]과 같으면 답은 7이 됩니다. [2], [4]와 같은 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]]
반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

#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]

C++에서 인수가 있는 이진 트리

예

입력

출력