leetcode

0 class Solution {

1 static const int MOD = 1E9 + 7;

2

3 static int binary_search(const vector<int> &arr, const int end, const int target) {

4 int low = 0, high = end - 1;

5 while (low <= high) {

6 const int mid = low + (high - low) / 2;

7 if (arr[mid] == target) return mid;

8 if (arr[mid] > target)

9 high = mid - 1;

10 else

11 low = mid + 1;

12 }

13 return -1;

14 }

15

16 public:

17 int numFactoredBinaryTrees(vector<int> &arr) const {

18 static int mem[1000];

19 memset(mem, 0x00, sizeof(mem));

20

21 sort(begin(arr), end(arr));

22 long long res = 0;

23 for (int i = 0; i < arr.size(); i++) {

24 const int crnt = arr[i];

25 long long local = 1;

26 for (int j = 0; j < i; j++) {

27 if (crnt % arr[j] != 0) continue;

28 const int idx = binary_search(arr, i, crnt / arr[j]);

29 if (idx == -1) continue;

30 local = (local + (long long)mem[j] * mem[idx]) % MOD;

31 }

32 mem[i] = local;

33 res = (res + mem[i]) % MOD;

34 }

35 return res;

36 }

37 };