ปัญหา
กำหนดอาร์เรย์จำนวนเต็มบวก A (ค่า > 1) สร้าง Binary Tree โดย:
- ใช้ตัวเลขใน A ได้ไม่จำกัดครั้ง
- โหนดที่ไม่ใช่ Leaf ต้องมีค่า = ผลคูณของลูก 2 ตัว
หาจำนวนต้นไม้ที่สร้างได้ Modulo 10^9 + 7
ตัวอย่าง: A = [2,4,5,10] → 7 ต้นไม้: [2], [4], [5], [10], [4,2,2], [10,2,5], [10,5,2]
แนวคิด: DP บนค่าที่เรียงแล้ว
State
dp[x] = จำนวนต้นไม้ที่ Root = x
Recurrence
เรียง A จากน้อยไปมาก สำหรับแต่ละ A[i]:
dp[A[i]] = 1 // ต้นไม้ Leaf เดียว
for j = 0 to i-1:
if A[i] % A[j] == 0:
right = A[i] / A[j]
if right ใน A:
dp[A[i]] += dp[A[j]] * dp[right]
โค้ด C++
#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; // Single node tree
for (int j = 0; j < i; j++) {
if (A[i] % A[j] == 0) {
int right = A[i] / A[j];
if (dp.count(right)) {
dp[A[i]] = add(dp[A[i]], mul(dp[A[j]], dp[right]));
}
}
}
ret = add(ret, dp[A[i]]);
}
return ret;
}
};
int main() {
Solution ob;
vector<int> v = {2, 4, 5, 10};
cout << ob.numFactoredBinaryTrees(v); // 7
return 0;
}
การทำงานตัวอย่าง
| Value | dp[value] | Trees |
|---|---|---|
| 2 | 1 | [2] |
| 4 | 2 | [4], [4,2,2] |
| 5 | 1 | [5] |
| 10 | 3 | [10], [10,2,5], [10,5,2] |
| Total | 7 |
ความซับซ้อน
- Time: O(n²) - คู่ i,j ทั้งหมด
- Space: O(n) - Hash Map
Input / Output
Input: [2,4,5,10]
Output: 7
