C++ में कारकों के साथ बाइनरी ट्री

मान लीजिए हमारे पास धनात्मक पूर्णांकों की एक सूची है; जिसका मान 1 से अधिक है। हम इन पूर्णांकों का उपयोग करके एक बाइनरी ट्री बनाएंगे, और प्रत्येक संख्या को जितनी बार चाहें उतनी बार उपयोग किया जा सकता है। प्रत्येक गैर-पत्ती नोड अपने बच्चों का उत्पाद होना चाहिए। तो हमें यह पता लगाना होगा कि हम कितने पेड़ बना सकते हैं? उत्तर मॉड्यूलो 10 ^ 9 + 7 में दिया जाएगा। इसलिए यदि इनपुट [2,4,5,10] जैसा है, तो उत्तर 7 होगा, क्योंकि हम [2], [4] जैसे 7 पेड़ बना सकते हैं। , [5], [10], [4,2,2], [10,2,5], [10,5,2]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• नक्शा डीपी परिभाषित करें
• सरणी को क्रमबद्ध करें A, n:=सरणी A का आकार, ret:=0
• मैं के लिए 0 से n - 1 की सीमा में
  • dp[A[i]] को 1 से बढ़ाएं
  • जे के लिए 0 से जे - 1 की सीमा में
    • अगर ए[i] मॉड ए[जे] =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]

आउटपुट

7