C++ এ ফ্যাক্টর সহ বাইনারি ট্রি

ধরুন আমাদের ধনাত্মক পূর্ণসংখ্যার একটি তালিকা আছে; যার মান 1 এর চেয়ে বেশি। আমরা এই পূর্ণসংখ্যাগুলি ব্যবহার করে একটি বাইনারি ট্রি করব এবং প্রতিটি সংখ্যা যতবার চাই ততবার ব্যবহার করা যেতে পারে। প্রতিটি নন-লিফ নোড তার বাচ্চাদের পণ্য হওয়া উচিত। তাহলে আমাদের খুঁজে বের করতে হবে আমরা কয়টি গাছ তৈরি করতে পারি? উত্তরটি মডিউল 10^9 + 7 এ দেওয়া হবে। সুতরাং যদি ইনপুটটি [2,4,5,10] এর মত হয়, তাহলে উত্তর হবে 7, যেমন আমরা 7টি গাছ তৈরি করতে পারি [2], [4] , [5], [10], [4,2,2], [10,2,5], [10,5,2]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি মানচিত্র ডিপি সংজ্ঞায়িত করুন
অ্যারে সাজান, n :=অ্যারের আকার, ret :=0
আমি 0 থেকে n – 1
- dp[A[i]] 1 দ্বারা বাড়ান
- 0 থেকে j – 1
  - যদি 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++ এ ফ্যাক্টর সহ বাইনারি ট্রি

উদাহরণ

ইনপুট

আউটপুট