Hard
题目描述
对于非负整数 x，其强力数组（powerful array）定义为最短的排序后的二的幂数组，这些二的幂的和等于 x。下表展示了强力数组的确定方法，可以证明 x 的强力数组是唯一的。
| num | 二进制表示 | 强力数组 |
|---|---|---|
| 1 | 00001 | [1] |
| 8 | 01000 | [8] |
| 10 | 01010 | [2, 8] |
| 13 | 01101 | [1, 4, 8] |
| 23 | 10111 | [1, 2, 4, 16] |
数组 big_nums 是通过按升序连接每个正整数 i 的强力数组创建的：1, 2, 3, 等等。因此，big_nums 开始为 [1, 2, 1, 2, 4, 1, 4, 2, 4, 1, 2, 4, 8, …]。
给定一个二维整数矩阵 queries，其中对于 queries[i] = [fromi, toi, modi]，你需要计算 (big_nums[fromi] * big_nums[fromi + 1] * … * big_nums[toi]) % modi。
返回一个整数数组 answer，其中 answer[i] 是第 i 个查询的答案。
示例 1：
输入：queries = [[1,3,7]]
输出：[4]
解释：
有一个查询。
big_nums[1..3] = [2,1,2]。它们的乘积是 4。结果是 4 % 7 = 4。
示例 2：
输入：queries = [[2,5,3],[7,7,4]]
输出：[2,2]
解释：
有两个查询。
第一个查询：big_nums[2..5] = [1,2,4,1]。它们的乘积是 8。结果是 8 % 3 = 2。
第二个查询：big_nums[7] = 2。结果是 2 % 4 = 2。
约束：
- 1 <= queries.length <= 500
- queries[i].length == 3
- 0 <= queries[i][0] <= queries[i][1] <= 10^15
- 1 <= queries[i][2] <= 10^5
解题思路
这是一道涉及位运算和二分搜索的困难题目。核心思路如下：
1. 理解强力数组： 每个数的强力数组就是其二进制表示中为1的位对应的2的幂。例如13 = 1101₂，对应强力数组[1, 4, 8]。
2. 构建big_nums逻辑： big_nums是所有正整数强力数组的连接。由于查询范围可达10¹⁵，无法直接构建数组，需要数学方法。
3. 关键函数设计：
countElements(n): 计算前n个数的强力数组总元素个数countBits(n, bit): 计算前n个数中第bit位为1的个数- 使用二分搜索找到查询区间对应的数字范围
4. 乘积计算优化： 由于所有元素都是2的幂，乘积等于2^(指数和)。只需统计各个位的出现次数，计算指数和，最后用快速幂取模。
5. 实现细节：
- 用二分搜索定位查询区间的起始和结束位置
- 分别处理完整数字和部分数字的贡献
- 使用位运算技巧高效计算各位出现次数
时间复杂度主要由二分搜索和位计算决定，空间复杂度为O(1)。
代码实现
class Solution {
public:
vector<int> findProductsOfElements(vector<vector<long long>>& queries) {
auto countElements = [&](long long n) -> long long {
long long result = 0;
for (int i = 0; i < 60; i++) {
result += countBits(n, i);
}
return result;
};
auto countBits = [&](long long n, int bit) -> long long {
long long cycle = 1LL << (bit + 1);
long long complete = n / cycle;
long long remainder = n % cycle;
long long result = complete * (1LL << bit);
if (remainder >= (1LL << bit)) {
result += remainder - (1LL << bit) + 1;
}
return result;
};
auto findKthElement = [&](long long k) -> pair<long long, int> {
long long left = 1, right = 1e15;
while (left < right) {
long long mid = left + (right - left) / 2;
if (countElements(mid) >= k) {
right = mid;
} else {
left = mid + 1;
}
}
long long num = left;
long long prev = (num > 1) ? countElements(num - 1) : 0;
int pos = k - prev - 1;
return {num, pos};
};
auto sumExponents = [&](long long from, long long to) -> vector<long long> {
vector<long long> exp(60, 0);
auto [fromNum, fromPos] = findKthElement(from + 1);
auto [toNum, toPos] = findKthElement(to + 1);
if (fromNum == toNum) {
int cnt = 0;
for (int i = 0; i < 60; i++) {
if ((fromNum >> i) & 1) {
if (cnt >= fromPos && cnt <= toPos) {
exp[i]++;
}
cnt++;
}
}
return exp;
}
// Handle fromNum partial
int cnt = 0;
for (int i = 0; i < 60; i++) {
if ((fromNum >> i) & 1) {
if (cnt >= fromPos) {
exp[i]++;
}
cnt++;
}
}
// Handle complete numbers
for (int i = 0; i < 60; i++) {
exp[i] += countBits(toNum - 1, i) - countBits(fromNum, i);
}
// Handle toNum partial
cnt = 0;
for (int i = 0; i < 60; i++) {
if ((toNum >> i) & 1) {
if (cnt <= toPos) {
exp[i]++;
}
cnt++;
}
}
return exp;
};
auto fastPow = [](long long base, long long exp, long long mod) -> long long {
long long result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp >>= 1;
}
return result;
};
vector<int> result;
for (auto& query : queries) {
long long from = query[0], to = query[1], mod = query[2];
vector<long long> exp = sumExponents(from, to);
long long totalExp = 0;
for (int i = 0; i < 60; i++) {
totalExp += exp[i] * i;
}
result.push_back(fastPow(2, totalExp, mod));
}
return result;
}
};
class Solution:
def findProductsOfElements(self, queries: List[List[int]]) -> List[int]:
def count_bits(n, bit):
cycle = 1 << (bit + 1)
complete = n // cycle
remainder = n % cycle
result = complete * (1 << bit)
if remainder >= (1 << bit):
result += remainder - (1 << bit) + 1
return result
def count_elements(n):
result = 0
for i in range(60):
result += count_bits(n, i)
return result
def find_kth_element(k):
left, right = 1, 10**15
while left < right:
mid = (left + right) // 2
if count_elements(mid) >= k:
right = mid
else:
left = mid + 1
num = left
prev = count_elements(num - 1) if num > 1 else 0
pos = k - prev - 1
return num, pos
def sum_exponents(from_idx, to_idx):
exp = [0] * 60
from_num, from_pos = find_kth_element(from_idx + 1)
to_num, to_pos = find_kth_element(to_idx + 1)
if from_num == to_num:
cnt = 0
for i in range(60):
if (from_num >> i) & 1:
if from_pos <= cnt <= to_pos:
exp[i] += 1
cnt += 1
return exp
# Handle from_num partial
cnt = 0
for i in range(60):
if (from_num >> i) & 1:
if cnt >= from_pos:
exp[i] += 1
cnt += 1
# Handle complete numbers
for i in range(60):
exp[i] += count_bits(to_num - 1, i) - count_bits(from_num, i)
# Handle to_num partial
cnt = 0
for i in range(60):
if (to_num >> i) & 1:
if cnt <= to_pos:
exp[i] += 1
cnt += 1
return exp
def fast_pow(base, exp, mod):
result = 1
base %= mod
while exp > 0:
if exp & 1:
result = (result * base) % mod
base = (base * base) % mod
exp >>= 1
return result
result = []
for from_idx, to_idx, mod in queries:
exp = sum_exponents(from_idx, to_idx)
total_exp = sum(exp[i] * i for i in range(60))
result.append(fast_pow(2, total_exp, mod))
return result
public class Solution {
public int[] FindProductsOfElements(long[][] queries) {
long CountBits(long n, int bit) {
long cycle = 1L << (bit + 1);
long complete = n / cycle;
long remainder = n % cycle;
long result = complete * (1L << bit);
if (remainder >= (1L << bit)) {
result += remainder - (1L << bit) + 1;
}
return result;
}
long CountElements(long n) {
long result = 0;
for (int i = 0; i < 60; i++) {
result += CountBits(n, i);
}
return result;
}
(long, int) FindKthElement(long k) {
long left = 1, right = (long)1e15;
while (left < right) {
long mid = left + (right - left) / 2;
if (CountElements(mid) >= k) {
right = mid;
} else {
left = mid + 1;
}
}
long num = left;
long prev = (num > 1) ? CountElements(num - 1) : 0;
int pos = (int)(k - prev - 1);
return (num, pos);
}
long[] SumExponents(long fromIdx, long toIdx) {
long[] exp = new long[60];
var (fromNum, fromPos) = FindKthElement(fromIdx + 1);
var (toNum, toPos) = FindKthElement(toIdx + 1);
if (fromNum == toNum) {
int cnt = 0;
for (int i = 0; i < 60; i++) {
if (((fromNum >> i) & 1) == 1) {
if (cnt >= fromPos && cnt <= toPos) {
exp[i]++;
}
cnt++;
}
}
return exp;
}
// Handle fromNum partial
int count = 0;
for (int i = 0; i < 60; i++) {
if (((fromNum >> i) & 1) == 1) {
if (count >= fromPos) {
exp[i]++;
}
count++;
}
}
// Handle complete numbers
for (int i = 0; i < 60; i++) {
exp[i] += CountBits(toNum - 1, i) - CountBits(fromNum, i);
}
// Handle toNum partial
count = 0;
for (int i = 0; i < 60; i++) {
if (((toNum >> i) & 1) == 1) {
if (count <= toPos) {
exp[i]++;
}
count++;
}
}
return exp;
}
long FastPow(long baseVal, long exp, long mod) {
long result = 1;
baseVal %= mod;
while (exp > 0) {
if ((exp & 1) == 1) {
result = (result * baseVal) % mod;
}
baseVal = (baseVal * baseVal) % mod;
exp >>= 1;
}
return result;
}
int[] result = new int[queries.Length];
for (int i = 0; i < queries.Length; i++) {
long fromIdx = queries[i][0];
long toIdx = queries[i][1];
long mod = queries[i][2];
long[] exp = SumExponents(fromIdx, toIdx);
long totalExp = 0;
for (int j = 0; j < 60; j++) {
totalExp += exp[j] * j;
}
result[i] = (int)FastPow(2, totalExp, mod);
}
return result;
}
}
var findProductsOfElements = function(queries) {
function countBits(x) {
let count = 0;
while (x > 0) {
count += x & 1;
x >>= 1;
}
return count;
}
function countElements(n) {
if (n <= 0) return 0;
let count = 0;
for (let i = 1; i <= n; i++) {
count += countBits(i);
}
return count;
}
function findKthElement(k) {
let left = 1, right = 2000000;
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (countElements(mid) >= k) {
right = mid;
} else {
left = mid + 1;
}
}
let num = left;
let prevCount = countElements(num - 1);
let pos = k - prevCount - 1;
let bits = [];
let temp = num;
while (temp > 0) {
if (temp & 1) bits.push(bits.length);
temp >>= 1;
}
return bits[pos];
}
function countPowers(n, power) {
if (n <= 0) return 0;
let count = 0;
for (let i = 1; i <= n; i++) {
let temp = i;
let bit = 0;
while (temp > 0) {
if ((temp & 1) && bit === power) {
count++;
}
temp >>= 1;
bit++;
}
}
return count;
}
function countPowersInRange(from, to) {
let powers = {};
for (let pos = from; pos <= to; pos++) {
let power = findKthElement(pos + 1);
powers[power] = (powers[power] || 0) + 1;
}
return powers;
}
function modPow(base, exp, mod) {
let result = 1;
base = base % mod;
while (exp > 0) {
if (exp % 2 === 1) {
result = (result * base) % mod;
}
exp = Math.floor(exp / 2);
base = (base * base) % mod;
}
return result;
}
return queries.map(([from, to, mod]) => {
let powers = countPowersInRange(from, to);
let result = 1;
for (let [power, count] of Object.entries(powers)) {
let base = modPow(2, parseInt(power), mod);
let contribution = modPow(base, count, mod);
result = (result * contribution) % mod;
}
return result;
});
};
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | - |
| 空间 | - |