Algorithm
Fancy Sequence
Solution
class Fancy:
def __init__(self):
self.mod = 10**9 + 7
self.v = list()
self.a = [1]
self.b = [0]
def quickmul(self, x: int, y: int) -> int:
return pow(x, y, self.mod)
def inv(self, x: int) -> int:
return self.quickmul(x, self.mod - 2)
def append(self, val: int) -> None:
self.v.append(val)
self.a.append(self.a[-1])
self.b.append(self.b[-1])
def addAll(self, inc: int) -> None:
self.b[-1] = (self.b[-1] + inc) % self.mod
def multAll(self, m: int) -> None:
self.a[-1] = self.a[-1] * m % self.mod
self.b[-1] = self.b[-1] * m % self.mod
def getIndex(self, idx: int) -> int:
if idx >= len(self.v):
return -1
a0 = self.a[-1] * self.inv(self.a[idx]) % self.mod
b0 = (self.b[-1] - self.b[idx] * a0) % self.mod
return (a0 * self.v[idx] + b0) % self.modTime Complexity
O(log m) for Append, O(1) for rest
Space Complexity
O(n)
