用指数的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