用指數的prefix sum去搞
後來想想 好像可以直接prefix product
應該就是這樣所以才很慢吧
我又想s了
def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
prefix = []
power, cur_sum = 0, 0
while n>0:
if (n&1)==1:
cur_sum += power
prefix.append(cur_sum)
n = n>>1
power += 1
prefix.append(0) #cur_sum[-1]=0
def poweroftwo(p):
res = 1
for i in range(p):
res = (res*2)%(10**9+7)
return res
res = []
for q in queries:
res.append(poweroftwo(prefix[q[1]]-prefix[q[0]-1]))
return res
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.132.58.28 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1754927340.A.393.html