# 2438. Range Product Queries of Powers
###### tags: `Leetcode` `Medium` `Prefix Sum` `Bit Manipulation` `Math`
Link: https://leetcode.com/problems/range-product-queries-of-powers/description/
## 思路
乍一看会觉得我们先算出来```powers``` array
里面装the minimum number of powers of 2 that sum to n
然后我们算prefix product
就可以得到结果
但实际上由于prefix product 最大值有可能到$2^{900}$ 没有哪个数据类型能存这么大的数
一个方法是我们不直接存powers of 2我们只存幂数
这样我们只需要做prefix Sum
同时我们还要维护一个powTable 里面放mod之后的power数
## Code

class Solution {
    public int[] productQueries(int n, int[][] queries) {
        List<Integer> pows = new ArrayList<>();
        for(int i=0; i<30; i++){
            if(((n>>i)&1)==1) pows.add(i);
        }
        List<Integer> prefix = new ArrayList<>();
        int sum = pows.get(0);
        prefix.add(sum);
        for(int i=1; i<pows.size(); i++){
            sum += pows.get(i);
            prefix.add(sum);
        }
        long[] powTable = new long[900];
        powTable[0]=1;
        int mod = 1000000007;
        for(int i=1; i<900; i++){
            powTable[i] = (powTable[i-1]*2)%mod;
        }
        int[] ans = new int[queries.length];
        for(int i=0; i<queries.length; i++){
            int p = prefix.get(queries[i][1])-(queries[i][0]!=0?prefix.get(queries[i][0]-1):0);
            ans[i] = (int)powTable[p];
        }
        return ans;
    }
}