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

初始理解题目

首先，我们需要清楚地理解题目在说什么。题目给出一个正整数 n，要求我们构造一个数组 powers，这个数组满足以下条件：

元素性质：数组中的每个元素都是 2 的幂。即，每个元素可以表示为 2^k，其中 k 是非负整数（k ≥ 0）。
和的条件：这些 2 的幂的和等于给定的 n。
最少数目：在所有满足上述条件的数组中，powers应该包含最少数量的元素。
非递减顺序：数组中的元素是按非递减顺序排列的，即对于任意 i < j，有 powers[i] ≤ powers[j]。
唯一性：在满足上述所有条件的情况下，构造 powers的方法是唯一的。

任何正整数 n都可以表示为若干个不同的2的幂的和，这实际上就是 n的二进制表示。例如：

5 的二进制是 101，可以表示为 4+1=5。

6 的二进制是 110，可以表示为 4+2=6。

7 的二进制是 111，可以表示为 4+2+1=7

在这种表示中，每个2的幂最多出现一次，因为二进制每一位只能是0或1。这种表示方法已经使用了最少数量的2的幂（因为不能合并相同的幂次）。

然而，题目允许数组中的元素可以重复（因为是非递减顺序，可以连续相同），但要求最少数目。这意味着我们需要尽可能合并相同的2的幂。

我们需要解决两个主要部分：

在前面的讨论中，我们已经明确了 powers的构造方法：将 n的二进制表示中所有为 1的位对应的2的幂按从小到大的顺序排列。例如：

构造 powers数组：给定一个正整数 n，构造一个由2的幂组成的、非递减的数组 powers，使得 powers中所有元素的和为 n，并且 powers中的元素数量尽可能少。这个数组是唯一的。

处理查询 queries：给定多个查询 queries[i] = [lefti, righti]，对于每个查询，我们需要计算 powers数组中从索引 lefti到 righti（包含两端）的所有元素的乘积，并将结果取余。

例如：

powers = [1, 4]，查询 [0, 1]→ 计算 1 * 4 = 4。
powers = [2, 4]，查询 [0, 0]→ 计算 2。

解决思路

构造 powers数组：

将 n转换为二进制遍历二进制的每一位，如果该位为 1，则将对应的2的幂加入 powers。
由于二进制是从低位到高位读取的，而 powers需要是非递减的，因此直接按从小到大的顺序添加即可。

预处理 powers的前缀积：

为了高效计算任意区间 [left, right]的乘积，可以预先计算 powers的前缀积数组 prefix。
prefix[0] = powers[0]
prefix[i] = prefix[i-1] * powers[i] % MOD（其中 MOD = 10^9 + 7）
这样，区间 [left, right]的乘积可以表示为 prefix[right] / prefix[left-1]（如果 left > 0），或者 prefix[right]（如果 left == 0）。
由于模运算中除法等同于乘以逆元，因此需要预先计算 prefix的逆元组 inv_prefix。

处理查询：

对于每个查询 [left, right]：
如果 left == 0，则结果为 prefix[right]。
否则，结果为 prefix[right] * inv_prefix[left-1] % MOD。
由于 prefix和 inv_prefix已经预先计算，每个查询可以在 O(1) 时间内完成

具体步骤

1.构造 powers数组：

初始化 powers = []。

power = 1（即 2的0次方）。

当 n > 0：

如果 n % 2 == 1，将 power加入 powers。

n = n // 2。

power = power * 2。

这样得到的 powers已经是非递减顺序。

2.计算前缀积 prefix：

初始化 prefix = [1] * len(powers)。

prefix[0] = powers[0] % MOD。

对于 i从 1到 len(powers)-1：

prefix[i] = (prefix[i-1] * powers[i]) % MOD。

3.计算逆元前缀积 inv_prefix：

逆元的计算可以通过费马小定理：inv(a) = pow(a, MOD-2, MOD)。

初始化 inv_prefix = [1] * len(powers)。

inv_prefix[-1] = pow(prefix[-1], MOD-2, MOD)。

对于 i从 len(powers)-2到 0：

inv_prefix[i] = (inv_prefix[i+1] * powers[i+1]) % MOD。

4.处理查询：

对于每个查询 [left, right]：

如果 left == 0：

answer = prefix[right]。

否则：

answer = (prefix[right] * inv_prefix[left-1]) % MOD。

将 answer加入 answers。

示例验证

示例1：

•
n = 5→ powers = [1, 4]。
•
prefix = [1, 4]（因为 1 % MOD = 1, 1 * 4 % MOD = 4）。
•
inv_prefix：
- •
  inv_prefix[1] = pow(4, MOD-2, MOD)。
- •
  inv_prefix[0] = (inv_prefix[1] * 4) % MOD。
假设 MOD = 10^9 + 7：
- •
  pow(4, MOD-2, MOD)是 4的逆元，即 x满足 4 * x ≡ 1 mod MOD。
- •
  计算得 inv_4 = 250000002（因为 4 * 250000002 = 1000000008 ≡ 1 mod 1000000007）。
- •
  inv_prefix[1] = 250000002。
- •
  inv_prefix[0] = (250000002 * 4) % MOD = 1。
•
查询 [0, 1]：
- •
  left = 0→ answer = prefix[1] = 4。
•
查询 [1, 1]：
- •
  left = 1→ answer = prefix[1] * inv_prefix[0] % MOD = 4 * 1 % MOD = 4。

示例2：

•
n = 6→ powers = [2, 4]。
•
prefix = [2, 8]。
•
inv_prefix：
- •
  inv_prefix[1] = pow(8, MOD-2, MOD)。
  - •
    inv_8 = 125000001（因为 8 * 125000001 = 1000000008 ≡ 1 mod 1000000007）。
- •
  inv_prefix[0] = (125000001 * 4) % MOD = 500000004（因为 125000001 * 4 = 500000004）。
•
查询 [0, 1]：
- •
  left = 0→ answer = prefix[1] = 8。
•
查询 [0, 0]：
- •
  left = 0→ answer = prefix[0] = 2。

边界情况

1.
n = 0：
- •
  题目中 n是正整数，不考虑。
2.
n = 1：
- •
  powers = [1]。
- •
  prefix = [1]。
- •
  查询 [0, 0]→ 1。
3.
查询的 left或 right超出 powers的索引范围：
- •
  题目中 queries是基于 powers的索引，假设输入是合法的。
4.
powers长度为1：
- •
  所有查询的 left和 right必须为 0。

代码实现

python

下载

复制

运行

MOD = 10**9 + 7def min_powers(n):powers = []power = 1while n > 0:if n % 2 == 1:powers.append(power)n = n // 2power = power * 2return powersdef solve(n, queries):powers = min_powers(n)m = len(powers)if m == 0:return [0] * len(queries)# Compute prefix productsprefix = [1] * mprefix[0] = powers[0] % MODfor i in range(1, m):prefix[i] = (prefix[i-1] * powers[i]) % MOD# Compute inverse prefix productsinv_prefix = [1] * minv_prefix[-1] = pow(prefix[-1], MOD-2, MOD)for i in range(m-2, -1, -1):inv_prefix[i] = (inv_prefix[i+1] * powers[i+1]) % MOD# Process queriesanswers = []for left, right in queries:if left == 0:res = prefix[right]else:res = (prefix[right] * inv_prefix[left-1]) % MODanswers.append(res)return answers

复杂度分析

1.
构造 powers：
- •
  时间：O(log n)，因为每次 n除以2。
- •
  空间：O(log n)，存储 powers。
2.
计算前缀积和逆元前缀积：
- •
  时间：O(m)，其中 m是 powers的长度（最多 log n）。
- •
  空间：O(m)，存储 prefix和 inv_prefix。
3.
处理查询：
- •
  每个查询 O(1)，总时间 O(q)，其中 q是查询数量。
- •
  空间：O(q)，存储结果。

总时间复杂度：O(log n + q)。

总空间复杂度：O(log n + q)。

优化

注意到 inv_prefix的计算可以优化：

•
inv_prefix[i] = pow(prefix[i], MOD-2, MOD)。
•
这样可以直接计算每个 prefix[i]的逆元，而不需要递推。
•
但递推的方法在模运算中更高效，因为 pow(a, MOD-2, MOD)的时间是 O(log MOD) ≈ 30 次运算。

示例运行

输入：

•
n = 5, queries = [[0, 1], [1, 1]]

步骤：

1.
powers = [1, 4]。
2.
prefix = [1, 4]。
3.
inv_prefix：
- •
  inv_prefix[1] = pow(4, MOD-2, MOD) = 250000002。
- •
  inv_prefix[0] = (250000002 * 4) % MOD = 1。
4.
查询：
- •
  [0, 1]：prefix[1] = 4。
- •
  [1, 1]：prefix[1] * inv_prefix[0] % MOD = 4 * 1 % MOD = 4。