Python 3 || Bisearch, count 1's and accumulate 0's
Intuition\n Describe your first thoughts on how to solve this problem. \nFirst, bi-search the number target in the big_nums before decomposition (i.e. [1,2,3,..
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFirst, bi-search the number `target` in the `big_nums` before decomposition (i.e. `[1,2,3,...]`) such that the index `bound` falls in its decmoposition.\n\nThen, count the accumulative number of 0\'s from `1` to `target-1`, plus the residual 0\'s in `target` (before `bound`).\n\nWith the number of 0\'s in `[low,high+1)`, answers to the queries are `pow(2,cnt,mod)`.\n\n# Approach\n\n`cnt1()`: Given a bound `num`, it returns the number of 1\'s from `1` to `num`. At each level `i`, there are `num // (1<<(i+1))` groups of 1\'s, each containing `1<<i` of 1\'s. Besides, for the last group, if ` cur  >= 1<<i`, it contains `cur+1 - (1<<i)` 1\'s.\n\n`acc0()`: Similar to `cnt1()`, we also count the 1\'s, but this time, each 1 at level `i` brings `i` of 0\'s into the accumulative count.\n\n**One little trick:** `target < bound`.We don\'t need to bisect from `10**15` each time, just bisect in `range(bound)`.\n\n# Complexity\n- Time complexity: $O(Q \\cdot \\log^2 M)$, where $Q$ is the length of `queries`, $M$ is the maximum bound in `queries`.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(Q)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python\nclass Solution:\n    def findProductsOfElements(self, queries: List[List[int]]) -> List[int]:\n        \n        def cnt1(num: int) -> int:\n            res = 0\n            for i in range(num.bit_length()):\n                cur = num % (1<<i+1)\n                res += (num-cur) // 2 \n                if cur >= 1<<i:\n                    res += cur+1 - (1<<i)\n            return res\n        \n        def acc0(num: int) -> int:\n            res = 0\n            for i in range(num.bit_length()):\n                cur = num % (1<<i+1)\n                res += (num-cur) // 2 * i\n                if cur >= 1<<i:\n                    res += (cur+1 - (1<<i)) * i\n            return res\n        \n        def count(bound: int) -> int:\n            # target is the number in the big_nums before decomposition that bound locates in\n            target = bisect_left(range(bound), bound, key=cnt1)\n\n            rest = bound - cnt1(target-1)\n            cnt = acc0(target-1)\n            \n            for i in range(target.bit_length()):\n                if target & (1<<i):\n                    cnt += i\n                    rest -= 1\n                    if not rest:    break\n\n            return cnt\n        \n        return [pow(2,count(high+1)-count(low),mod) for low,high,mod in queries]\n```
['Binary Search', 'Bit Manipulation', 'Python3']