每日一题-20250811

发表于 阅读次数： 本文字数： 156 阅读时长 ≈ 1 分钟

Leetcode

2438. 二的幂数组中查询范围内的乘积/第 89 场双周赛 Q2/Rating 1610

  • 位运算
  • 前缀和
  • 快速幂

考虑到 2a×2b=2a+b2^a \times 2^b = 2^{a + b}，所以可以对指数做前缀和，然后快速幂求解。

也可以不做前缀和，每次进行求和，然后快速幂求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
MOD = 10 ** 9 + 7

def qp(x: int, k: int) -> int:
    ans = 1
    while k:
        if k & 1:
            ans = (ans * x) % MOD
        x = (x * x) % MOD
        k >>= 1
    return ans % MOD

class Solution:
    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        p = []
        for i in range(30):
            if n & (1 << i):
                p.append(i)
        ans = []
        for l, r in queries:
            ans.append(qp(2, sum(p[l:r+1])))
        return ans