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數組，并預處理前綴積和逆元前綴積，然后對每個查詢計算區間乘積并取余，最后返回所有查詢的結果。