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.mod

Time Complexity

O(log m) for Append, O(1) for rest

Space Complexity

O(n)
Put Your Ad HereReach thousands of highly targeted software engineers. Click to inquire.