Complicated recurrence, faster than 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nThe answer is a power of 2 modulo the given mod. It suffices to keep track of the power
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe answer is a power of 2 modulo the given mod. It suffices to keep track of the power of 2 and further it suffices to compute the total power of 2 from the start of the array up to each given index, then subtract the lower bound from the upper bound.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nHere is the derivation of the recurrence relation.\nSuppose we have an array with the representation of a consecutive sequence of numbers. Each representation ends with a fixed suffix $prd\\_lst$ of length $x$, where $x$ can be $0$.\nFor example, such a list can be\n$$\n4, 1, 4, 2, 4, 1, 2, 4\n$$\nas given in the problem. Here $x=1$ and the suffix is $4$. The list starts with the suffix itself, then (1, 4), (2, 4), (1, 2, 4), $\\ldots$, each term being the binary representation of some number ending in the suffix.\n\nThis is a slight generalization of the initial problem, but is easier to solve because we can use recursion. In the initial problem, $x=0$ and there is no suffix.\n\nThe problem is determining the product of all numbers up to the $a$-th position in this list.\nIf $a \\leq x$, then we take the product of some subsequence of $prd\\_lst$.\nOtherwise, we consider sublists of this list, of length\n$$\n\\ell_0=x,\\ \\ell_{k+1}=2\\ell_k+2^k.\n$$\nIn the example above, the sublists are\n$$\n\\{4\\},\\ \\{4, 1, 4\\}, \\{4, 1, 4, 2, 4, 1, 2, 4\\},\n$$\nof length $\\ell_0=1$, $\\ell_1=2\\cdot 1+2^0=3$, $\\ell_3=2\\cdot 3+2^1=8$.\nEach sublist contains all the numbers up to a certain last binary digit: the first one is going up to $0$, the second one is going up to $1$, the third one is going up to $2$.\n\nEach new sublist contains two copies of the previous sublist, namely one identical copy in the beginning followed by one modified copy in which each listing has an extra suffix. For example, the sublist corresponding to $k=2$\n$$\n4, 1, 4, 2, 4, 1, 2, 4\n$$\ncontains one identical copy of the previous sublist $4,(1,4)$, followed by a modified copy in which the suffix $4$ is replaced by $2,4$. The second half has $2^{k-1}$ extra values of $2^{k-1}=2$.\nIn the same way, we can count the total power of $2$ in each sublist, which is given by the recurrence relation\n$$\np_0=prod,\\ p_{k+1}=2*p_0+k \\cdot 2^k.\n$$\nHere $prod$ is the power of $2$ in the product of the elements in the suffix $prod\\_lst$. The $k+1$-th sublist always contains two copies of the $k$-th sublist and has $2^k$ extra elements equal to $2^k$.\n\nWhen computing the product of all elements up to $a$, we look for the longest sublist such that $\\ell_k<a$. The answer contains the computed value of $p_k$ and we then use recursion for the next segment from $\\ell_k+1$ to $a$.\nThis second computation uses exactly the same method, but $a$ is replaced by $a-\\ell_k$, we increase $x$ by $1$, and we include $2^k$ in the suffix.\n\nThis algorithm is used in the program below.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nOn the latest run, this solution ran in 119ms.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def findProductsOfElements(self, queries: List[List[int]]) -> List[int]:\n        @cache\n        def pr(a):\n            return pro(a, 0, 0, ())\n        def pro(a, x, prd, prd_lst):\n            if a<=x:\n                return sum(prd_lst[:a])\n            k=0\n            ans=prd\n            l=x\n            nxt=(l<<1)+(1<<k)\n            while nxt<a:\n                l=nxt\n                ans=(ans<<1)+(k<<k)\n                k+=1\n                nxt=(l<<1)+(1<<k)\n            return ans+pro(a-l, x+1, prd+k, (k,)+prd_lst)\n        return [pow(2, pr(b+1)-pr(a), p) for a, b, p in queries] \n```
['Python3']