每日一題：2的冪數組中查詢范圍內的乘積；快速冪算法

題目選自2438. 二的冪數組中查詢范圍內的乘積

還是一樣的，先講解思路，然后再說代碼。

題目有一定難度，所以我要爭取使所有人都能看懂，用的方法會用最常規的思想。關于語言，都是互通的，只要你懂了一門語言，可以做到盡量理解其他語言。

每一次頭腦風暴都是一次十足的成長，請有耐心，即使是小白，看完自有收獲。

這道題跟之前那道題目重新排序得到 2 的冪呼應起來了，沒有看過的可以先去看一下前面那道題。

題目

給你一個正整數?n?，你需要找到一個下標從?0?開始的數組?powers?，它包含?最少?數目的?2?的冪，且它們的和為?n?。powers?數組是?非遞減?順序的。根據前面描述，構造?powers?數組的方法是唯一的。

同時給你一個下標從?0?開始的二維整數數組?queries?，其中?queries[i] = [lefti, righti]?，其中?queries[i]?表示請你求出滿足?lefti <= j <= righti?的所有?powers[j]?的乘積。

請你返回一個數組?answers?，長度與?queries?的長度相同，其中?answers[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] 。沒法得到元素數目更少的數組。
第 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 。
每個答案對 109 + 7 取余得到的結果都相同，所以返回 [2,4,64] 。

示例 2：

輸入：n = 2, queries = [[0,0]]
輸出：[2]
解釋：
對于 n = 2, powers = [2] 。
唯一一個查詢的答案是 powers[0] = 2 。答案對 109 + 7 取余后結果相同，所以返回 [2] 。

題目解析

（題目意思很簡單，但是給這個題目做翻譯的人翻譯的很差勁，所以得重新譯一遍）

給你一個正整數?n，你需要找到一個數組?powers。這個數組包含若干個 2 的冪（比如 1, 2, 4, 8, 16...），它們加起來正好等于?n。并且，powers?數組要用最少數量的 2 的冪，同時數組里的數必須是從小到大排列的（非遞減）。題目保證這種找法是唯一的。

然后，你還得到一個二維數組?queries，里面每個元素是?[left, right]。對于每一個?[left, right]，你需要計算?powers?數組中從?left下標到?right下標（包含兩端）的所有數字的乘積。

最后，因為乘積可能會非常大，所以你計算出來的每個乘積都要對 10^9 + 7 取余。最后把所有查詢的結果放在一個數組里返回。

1.題目與“2的冪”關聯

這個正整數n是這個數組相加起來的結果，很容易想到每一個數都有它相對應的二進制數。

例如，數字 13。它的二進制是?1101

2.powers數組是由2的冪組成的

每一個數都有它相對應的唯一二進制數，我們只需要把在?n?的二進制表示中出現的那些 2^k?找出來，然后按從小到大的順序排列就行了

比如?n = 15，二進制是?1111，表示?15 = 8+4+2+1 = 2^3 + 2^2 + 2^1 + 2^0，所以?powers = [1, 2, 4, 8]。
比如?n = 12，二進制是?1100，表示?12 = 2^3 + 2^2，所以?powers = [4, 8]。

3.如何處理查詢?`queries？`

1.對于每個?[left, right]，計算?powers[left] * powers[left+1] * ... * powers[right]?對 10^9 + 7取余。

我們可以寫一個循環，從?left?遍歷到?right，把每個?powers[j]?乘起來，每乘一次就取余。

# 偽代碼
product = 1
for j from left to right:product = (product * powers[j]) % MOD

2.如果?queries?很多，或者?right - left?的距離很大，上面的循環可能會有點慢。有沒有更快的辦法？

所以我們需要利用指數的性質：2^a * 2^b = 2^(a+b)。

也就是說，我們可以把?powers?數組中的每個元素看成是?2?的某個次方，計算乘積時只需要把這些次方加起來，然后再計算?2?的這個總次方。比如?powers = [1, 2, 4, 8]，其實是?[2^0, 2^1, 2^2, 2^3]，查詢?[0, 2]?的乘積是?2^0 * 2^1 * 2^2 = 2^(0+1+2) = 2^3 = 8。

這樣可以避免直接計算大數。

4.如何快速計算?`2`?的高次方并取模？

我們需要計算?2^x mod (10^9 + 7)，其中?x?可能很大。
直接用?2^x?會溢出，所以需要用到快速冪算法

快速冪的核心思想是把指數表示成二進制形式，每次只處理一位。（后面代碼解析會詳細說明語法）

完整代碼

class Solution(object):def productQueries(self, n, queries):""":type n: int:type queries: List[List[int]]:rtype: List[int]"""MOD = 10**9 + 7# 第一步：把 n 表示成 2 的冪的和，得到 powers 數組powers = []power = 0while n > 0:if n & 1:  # 如果 n 的最低位是 1powers.append(1 << power)  # 加入 2^powern >>= 1  # n 右移一位power += 1# 第二步：把 powers 數組中的每個元素表示成 2 的指數# 比如 powers = [1, 2, 4, 8] 表示成 exponents = [0, 1, 2, 3]exponents = []for p in powers:exp = 0while (1 << exp) != p:exp += 1exponents.append(exp)# 第三步：快速冪算法，計算 2^x mod MODdef quick_pow(base, exp, mod):if exp == 0:return 1result = 1base %= modwhile exp > 0:if exp & 1:  # 如果 exp 的最低位是 1result = (result * base) % modbase = (base * base) % modexp >>= 1return result# 第四步：處理每個查詢answers = []for left, right in queries:# 計算范圍內所有指數的和total_exp = sum(exponents[left:right + 1])# 用快速冪計算 2^total_exp mod MODresult = quick_pow(2, total_exp, MOD)answers.append(result)return answers

代碼解析

代碼結構

代碼分為四個主要部分：

把?n?表示成 2 的冪的和，得到?powers?數組。
把?powers?數組中的每個元素表示成 2 的指數，得到?exponents?數組。
實現快速冪算法，用于計算?2^x mod MOD。
處理每個查詢，計算答案。

詳細解析

第一部分：得到?powers?數組
```
powers = []
power = 0
while n > 0:if n & 1:  # 如果 n 的最低位是 1powers.append(1 << power)  # 加入 2^powern >>= 1  # n 右移一位power += 1
```
- 這一部分的作用是把?n?表示成 2 的冪的和。
- n & 1?是位運算，檢查?n?的最低位是否為 1。如果是 1，說明需要加入?2^power。
- 1 << power?是位運算，表示?2^power。
- n >>= 1?是位運算，把?n?右移一位，相當于除以 2。
- 比如?n = 15，二進制是?1111，循環過程如下：
  - 第一輪：n = 1111，最低位是 1，加入?2^0 = 1，n?右移變成?111。
  - 第二輪：n = 111，最低位是 1，加入?2^1 = 2，n?右移變成?11。
  - 第三輪：n = 11，最低位是 1，加入?2^2 = 4，n?右移變成?1。
  - 第四輪：n = 1，最低位是 1，加入?2^3 = 8，n?右移變成?0。
  - 結束，得到?powers = [1, 2, 4, 8]。
第二部分：得到?exponents?數組
```
exponents = []
for p in powers:exp = 0while (1 << exp) != p:exp += 1exponents.append(exp)
```
- 這一部分的作用是把?powers?數組中的每個元素表示成 2 的指數。
- 比如?powers = [1, 2, 4, 8]，我們需要得到?exponents = [0, 1, 2, 3]，因為?1 = 2^0, 2 = 2^1, 4 = 2^2, 8 = 2^3。
- 對于每個?p，我們用一個循環找到?exp，使得?2^exp == p。
第三部分：快速冪算法
```
def quick_pow(base, exp, mod):if exp == 0:return 1result = 1base %= modwhile exp > 0:if exp & 1:  # 如果 exp 的最低位是 1result = (result * base) % modbase = (base * base) % modexp >>= 1return result
```
- 這一部分的作用是快速計算?base^exp mod mod。
- 直接計算?base^exp?可能會導致數字非常大（比如?2^100），所以我們用快速冪算法。
- 快速冪的核心思想是把指數?exp?表示成二進制形式，每次只處理一位。
- 比如要計算?2^10 mod 1000000007：
  - 10?的二進制是?1010。
  - 從低位到高位處理：
    - 第 0 位是 0，不用乘。
    - 第 1 位是 1，乘上?2^2。
    - 第 2 位是 0，不用乘。
    - 第 3 位是 1，乘上?2^8。
  - 每次處理時，base?都會平方（base = base * base），這樣可以快速得到高次方的值。
  - 每次乘法后都對?mod?取模，避免數字過大。
第四部分：處理查詢
```
answers = []
for left, right in queries:# 計算范圍內所有指數的和total_exp = sum(exponents[left:right + 1])# 用快速冪計算 2^total_exp mod MODresult = quick_pow(2, total_exp, MOD)answers.append(result)
```
- 這一部分的作用是處理每個查詢。
- 對于每個查詢?[left, right]，我們需要計算?powers[left] * powers[left+1] * ... * powers[right]。
- 因為?powers?中的每個元素是?2?的某個次方，所以乘積可以表示成?2?的指數之和。
- 比如?powers = [1, 2, 4, 8]，exponents = [0, 1, 2, 3]，查詢?[0, 2]：
  - 取出?exponents[0:3] = [0, 1, 2]。
  - 計算指數之和：0 + 1 + 2 = 3。
  - 計算?2^3 mod 1000000007 = 8。
  - 答案是 8。
- 最后把所有答案存入?answers?數組。

時間復雜度

第一部分：得到?powers?數組
- 我們用一個 while 循環處理?n，每次把?n?右移一位，直到?n?變成 0。
- n?的二進制表示有?log n?位（因為 2 的多少次方可以表示 n）。
- 所以這一部分的時間復雜度是?O(log n)。
第二部分：得到?exponents?數組
- 對于?powers?數組中的每個元素?p，我們用一個 while 循環找到對應的指數?exp。
- powers?數組的長度最多是?log n（因為?n?的二進制表示最多有?log n?位 1）。
- 對于每個?p，找到?exp?的循環次數最多是?log p，而?p?最大是?n，所以最壞情況下是?O(log n)。
- 總的時間復雜度是?O(log n * log n)，但實際上?p?的值是遞增的，平均復雜度更低。
第三部分：快速冪算法
- 快速冪算法的時間復雜度是?O(log exp)，因為我們把指數?exp?表示成二進制形式，每次處理一位。
- 在我們的題目中，exp?是指數之和，最壞情況下可能是?O(log n)?級別的（因為?n?本身是 2 的冪的和）。
第四部分：處理查詢
- 假設有?q?個查詢（q?是?queries?的長度）。
- 對于每個查詢，我們需要計算范圍內指數的和，時間復雜度是?O(log n)（因為?powers?數組的長度最多是?log n）。
- 然后用快速冪計算結果，時間復雜度是?O(log exp)，其中?exp?最壞情況下是?O(log n)。
- 所以每個查詢的復雜度是?O(log n)。
- 總的時間復雜度是?O(q * log n)。