Medium
题目描述
给定一个正整数 n，存在一个下标从 0 开始的数组 powers，该数组由能够相加得到 n 的最少数量的 2 的幂次方组成。该数组按非递减顺序排列，并且只有一种方式构成该数组。
同时给你一个下标从 0 开始的二维整数数组 queries，其中 queries[i] = [lefti, righti]。每个 queries[i] 表示一个查询，你需要找到所有满足 lefti <= j <= righti 的 powers[j] 的乘积。
返回一个数组 answers，长度与 queries 相等，其中 answers[i] 是第 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]。可以证明 powers 不能有更小的大小。
第 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^91 <= queries.length <= 10^50 <= starti <= endi < powers.length
解题思路
这道题需要我们理解两个关键点：
构建powers数组：根据n的二进制表示，每个为1的位对应一个2的幂次方。例如n=15的二进制是1111，对应powers=[1,2,4,8]。
计算范围乘积：对于每个查询[left,right]，需要计算powers[left]到powers[right]的乘积。
解题思路：
首先，我们通过分析n的二进制表示来构建powers数组。从最低位开始检查，如果第i位为1，则2^i应该包含在powers数组中。
然后，对于每个查询，我们可以直接遍历指定范围内的元素计算乘积。由于2的幂次方相乘等于指数相加，我们可以先计算指数和，再用快速幂求结果，这样可以避免大数乘法的精度问题。
为了处理大数取模，我们使用模运算的性质：(a * b) % MOD = ((a % MOD) * (b % MOD)) % MOD。
优化方案：
- 方法1：直接遍历计算乘积（简单直接）
- 方法2：计算指数和后用快速幂（推荐，避免溢出）
代码实现
class Solution {
public:
vector<int> productQueries(int n, vector<vector<int>>& queries) {
const int MOD = 1000000007;
vector<int> powers;
// 构建powers数组
for (int i = 0; i < 32; i++) {
if ((n >> i) & 1) {
powers.push_back(i);
}
}
// 快速幂函数
auto quickPow = [&](long long base, long long exp) -> long long {
long long result = 1;
while (exp > 0) {
if (exp & 1) {
result = (result * base) % MOD;
}
base = (base * base) % MOD;
exp >>= 1;
}
return result;
};
vector<int> answers;
for (auto& query : queries) {
int left = query[0], right = query[1];
long long totalExp = 0;
// 计算指数和
for (int i = left; i <= right; i++) {
totalExp += powers[i];
}
// 计算2^totalExp % MOD
answers.push_back(quickPow(2, totalExp));
}
return answers;
}
};
class Solution:
def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
MOD = 10**9 + 7
# 构建powers数组（存储指数）
powers = []
i = 0
while n > 0:
if n & 1:
powers.append(i)
n >>= 1
i += 1
answers = []
for left, right in queries:
# 计算指数和
total_exp = sum(powers[left:right+1])
# 计算2^total_exp % MOD
answers.append(pow(2, total_exp, MOD))
return answers
public class Solution {
public int[] ProductQueries(int n, int[][] queries) {
const int MOD = 1000000007;
var powers = new List<int>();
// 构建powers数组
for (int i = 0; i < 32; i++) {
if ((n >> i & 1) == 1) {
powers.Add(i);
}
}
var answers = new int[queries.Length];
for (int q = 0; q < queries.Length; q++) {
int left = queries[q][0], right = queries[q][1];
long totalExp = 0;
// 计算指数和
for (int i = left; i <= right; i++) {
totalExp += powers[i];
}
// 计算2^totalExp % MOD
answers[q] = (int)QuickPow(2, totalExp, MOD);
}
return answers;
}
private long QuickPow(long baseNum, long exp, int mod) {
long result = 1;
while (exp > 0) {
if ((exp & 1) == 1) {
result = (result * baseNum) % mod;
}
baseNum = (baseNum * baseNum) % mod;
exp >>= 1;
}
return result;
}
}
var productQueries = function(n, queries) {
const MOD = 1000000007;
const powers = [];
// 构建powers数组
for (let i = 0; i < 32; i++) {
if ((n >> i) & 1) {
powers.push(i);
}
}
// 快速幂函数
const quickPow = (base, exp) => {
let result = 1n;
base = BigInt(base);
exp = BigInt(exp);
const modBig = BigInt(MOD);
while (exp > 0n) {
if (exp & 1n) {
result = (result * base) % modBig;
}
base = (base * base) % modBig;
exp >>= 1n;
}
return Number(result);
};
const answers = [];
for (const [left, right] of queries) {
let totalExp = 0;
// 计算指数和
for (let i = left; i <= right; i++) {
totalExp += powers[i];
}
// 计算2^totalExp % MOD
answers.push(quickPow(2, totalExp));
}
return answers;
};
复杂度分析
| 复杂度类型 | 复杂度分析 |
|---|---|
| 时间复杂度 | O(log n + Q × k)，其中 Q 是查询数量，k 是 powers 数组的平均查询范围长度，log n 是构建 powers 数组的时间 |
| 空间复杂度 | O(log n)，用于存储 powers 数组，最多有 log n 个元素 |