Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Every global addition and multiplication can be combined into one affine transformation: a stored base value currently means base * mul + add, modulo M = 10^9 + 7. New values must be converted back into this base coordinate system so earlier operations do not affect them retroactively.

Approach

Start with mul = 1 and add = 0. For append(val), store (val - add) * inverse(mul) modulo M. For addAll, increase add. For multAll(m), multiply both mul and add by m. For a valid index, apply the current transformation to its stored base; return -1 for an out-of-range index. The allowed multipliers are positive and smaller than the prime modulus, so mul stays nonzero modulo M and its inverse exists.

MOD = 10**9 + 7

class Fancy:
    def __init__(self):
        self.arr = []
        self.add = 0
        self.mul = 1

    def append(self, val: int) -> None:
        base = ((val - self.add) * pow(self.mul, -1, MOD)) % MOD
        self.arr.append(base)

    def addAll(self, inc: int) -> None:
        self.add = (self.add + inc) % MOD

    def multAll(self, m: int) -> None:
        self.mul = (self.mul * m) % MOD
        self.add = (self.add * m) % MOD

    def getIndex(self, idx: int) -> int:
        if idx >= len(self.arr):
            return -1
        return (self.arr[idx] * self.mul + self.add) % MOD

# Your Fancy object will be instantiated and called as such:
# obj = Fancy()
# obj.append(val)
# obj.addAll(inc)
# obj.multAll(m)
# param_4 = obj.getIndex(idx)

Complexity analysis

Let q be the number of appended values and M = 10^9 + 7. In the unit-cost modular-arithmetic model, append takes amortized O(log M) time for inversion and dynamic-array insertion; addAll, multAll and getIndex take O(1) time. Python uses modular inversion, while JavaScript computes the inverse by binary exponentiation. Persistent storage is O(q), with O(1) arithmetic workspace. An individual append may additionally require O(q) time and temporary storage when the backing array grows; this does not change the amortized bound or O(q) total space.