0823.cpp (1172B)
1 class Solution { 2 static const int MOD = 1E9 + 7; 3 4 static int binary_search(const vector<int> &arr, const int end, const int target) { 5 int low = 0, high = end - 1; 6 while (low <= high) { 7 const int mid = low + (high - low) / 2; 8 if (arr[mid] == target) return mid; 9 if (arr[mid] > target) 10 high = mid - 1; 11 else 12 low = mid + 1; 13 } 14 return -1; 15 } 16 17 public: 18 int numFactoredBinaryTrees(vector<int> &arr) const { 19 static int mem[1000]; 20 memset(mem, 0x00, sizeof(mem)); 21 22 sort(begin(arr), end(arr)); 23 long long res = 0; 24 for (int i = 0; i < arr.size(); i++) { 25 const int crnt = arr[i]; 26 long long local = 1; 27 for (int j = 0; j < i; j++) { 28 if (crnt % arr[j] != 0) continue; 29 const int idx = binary_search(arr, i, crnt / arr[j]); 30 if (idx == -1) continue; 31 local = (local + (long long)mem[j] * mem[idx]) % MOD; 32 } 33 mem[i] = local; 34 res = (res + mem[i]) % MOD; 35 } 36 return res; 37 } 38 };