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

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

初始理解题目

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

1. 元素性质​：数组中的每个元素都是 2 的幂。即，每个元素可以表示为 2^k，其中 k 是非负整数（k ≥ 0）。

2. ​和的条件​：这些 2 的幂的和等于给定的 n。

3. ​最少数目​：在所有满足上述条件的数组中，powers应该包含最少数量的元素。

4. 非递减顺序​：数组中的元素是按非递减顺序排列的，即对于任意 i < j，有 powers[i] ≤ powers[j]。
5. 唯一性​：在满足上述所有条件的情况下，构造 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. 1.

   ​n = 0​：

   • •

     题目中 n是正整数，不考虑。

2. 2.

   ​n = 1​：

   • •

     powers = [1]。

   • •

     prefix = [1]。

   • •

     查询 [0, 0]→ 1。

3. 3.

   ​查询的 left或 right超出 powers的索引范围​：

   • •

     题目中 queries是基于 powers的索引，假设输入是合法的。

4. 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. 1.

   ​构造 powers​：

   • •

     时间：O(log n)，因为每次 n除以2。

   • •

     空间：O(log n)，存储 powers。

2. 2.

   ​计算前缀积和逆元前缀积​：

   • •

     时间：O(m)，其中 m是 powers的长度（最多 log n）。

   • •

     空间：O(m)，存储 prefix和 inv_prefix。

3. 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. 1.

   powers = [1, 4]。

2. 2.

   prefix = [1, 4]。

3. 3.

   inv_prefix：

   • •

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

   • •

     inv_prefix[0] = (250000002 * 4) % MOD = 1。

4. 4.

   查询：

   • •

     [0, 1]：prefix[1] = 4。

   • •

     [1, 1]：prefix[1] * inv_prefix[0] % MOD = 4 * 1 % MOD = 4。

​输出​：

[4, 4]

最终答案

对于给定的 n和 queries，按照上述方法构造 powers数组，并预处理前缀积和逆元前缀积，然后对每个查询计算区间乘积并取余，最后返回所有查询的结果。