leetcode 2438. 二的幂数组中查询范围内的乘积 中等

给你一个正整数 n ，你需要找到一个下标从 0 开始的数组 powers ，它包含 最少 数目的 2 的幂，且它们的和为 n 。powers 数组是 非递减 顺序的。根据前面描述，构造 powers 数组的方法是唯一的。

同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [lefti, righti] ，其中 queries[i] 表示请你求出满足 lefti <= j <= righti 的所有 powers[j] 的乘积。

请你返回一个数组 answers ，长度与 queries 的长度相同，其中 answers[i]是第 i 个查询的答案。由于查询的结果可能非常大，请你将每个 answers[i] 都对 10^9 + 7 取余 。

示例 1：

输入：n = 15, queries = [[0,1],[2,2],[0,3]]
输出：[2,4,64]
解释：
对于 n = 15 ，得到 powers = [1,2,4,8] 。没法得到元素数目更少的数组。
第 1 个查询的答案：powers[0] * powers[1] = 1 * 2 = 2 。
第 2 个查询的答案：powers[2] = 4 。
第 3 个查询的答案：powers[0] * powers[1] * powers[2] * powers[3] = 1 * 2 * 4 * 8 = 64 。
每个答案对 10^9 + 7 得到的结果都相同，所以返回 [2,4,64] 。

示例 2：

输入：n = 2, queries = [[0,0]]
输出：[2]
解释：
对于 n = 2, powers = [2] 。
唯一一个查询的答案是 powers[0] = 2 。答案对 10^9 + 7 取余后结果相同，所以返回 [2] 。

提示：

• 1 <= n <= 10^9
• 1 <= queries.length <= 10^5
• 0 <= starti <= endi < powers.length

分析：由于 n 最大值为 10 的 9 次方，可以先打表记录所有小于等于 10 的 9 次方的 2 的幂，并构造 power 数组。接着遍历 queries 数组，每次根据 left 和 right 求出对应答案并取模。构造出的 power 数组最多不超过 30 个数，因此每次求答案的乘法也不超过 30 次。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* productQueries(int n, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    int t=0;
    int power[35]={0},pow_2[35]={1};
    for(int i=1;i<30;++i)
        pow_2[i]=pow_2[i-1]*2;
    for(int i=29;i>=0&&n>0;--i)
        if(n>=pow_2[i])power[t++]=pow_2[i],n-=pow_2[i];
    for(int i=0,j=t-1;i<j;i++,j--)
    {
        int temp=power[i];
        power[i]=power[j],power[j]=temp;
    }

    *returnSize=queriesSize;
    int *ans=(int*)malloc(sizeof(int)*queriesSize);
    long long cnt=1,mod=1e9+7;
    for(int i=0;i<queriesSize;++i)
    {
        cnt=1;
        for(int j=queries[i][0];j<=queries[i][1];++j)
            cnt=cnt*(long long)power[j]%mod;
        ans[i]=cnt%mod;;
    }
    
    return ans;
}