ต้นไม้ไบนารีพร้อมปัจจัยใน 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
  • เพิ่ม dp[A[i]] ขึ้น 1
  • สำหรับ j ในช่วง 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]

ผลลัพธ์

7