Fancy Sequence

hard design modular inverse lazy update number theory

Problem

Design a Fancy class with four operations. append(val) adds val to the end. addAll(inc) increases every existing value by inc. multAll(m) multiplies every existing value by m. getIndex(idx) returns the current value at idx modulo 10⁹+7, or -1 if the index is out of range. Up to 10⁵ calls — each must be near O(1).

Inputappend 2, addAll 3, append 7, multAll 2, getIndex 0

Output10

[2] → [5] → [5,7] → [10,14]; getIndex(0) = 10. Later addAll 3, append 10, multAll 2 give [26,34,20].

operations (one per token: a=append, +=addAll, *=multAll, ?=getIndex; e.g. a2 +3 a7 *2 ?0)

MOD = 10**9 + 7

class Fancy:
    def __init__(self):
        self.seq = []      # normalized stored values
        self.mult = 1      # global multiplier
        self.add = 0       # global addend

    def append(self, val):
        # store so that (stored*mult + add) == val
        inv = pow(self.mult, MOD - 2, MOD)
        self.seq.append((val - self.add) * inv % MOD)

    def addAll(self, inc):
        self.add = (self.add + inc) % MOD

    def multAll(self, m):
        self.mult = self.mult * m % MOD
        self.add = self.add * m % MOD

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

const MOD = 1000000007n;

function power(b, e) {            // modular exponentiation
  let r = 1n; b %= MOD;
  while (e > 0n) {
    if (e & 1n) r = r * b % MOD;
    b = b * b % MOD; e >>= 1n;
  }
  return r;
}

class Fancy {
  constructor() { this.seq = []; this.mult = 1n; this.add = 0n; }
  append(val) {                  // store so stored*mult + add == val
    const inv = power(this.mult, MOD - 2n);
    this.seq.push((BigInt(val) - this.add + MOD) % MOD * inv % MOD);
  }
  addAll(inc) { this.add = (this.add + BigInt(inc)) % MOD; }
  multAll(m) {
    this.mult = this.mult * BigInt(m) % MOD;
    this.add = this.add * BigInt(m) % MOD;
  }
  getIndex(idx) {                // rebuild value at idx
    if (idx >= this.seq.length) return -1;
    return Number((this.seq[idx] * this.mult + this.add) % MOD);
  }
}

class Fancy {
    static final long MOD = 1_000_000_007L;
    long[] seq = new long[100005];
    int n = 0;
    long mult = 1, add = 0;

    long power(long b, long e) {           // modular exponentiation
        long r = 1; b %= MOD;
        while (e > 0) {
            if ((e & 1) == 1) r = r * b % MOD;
            b = b * b % MOD; e >>= 1;
        }
        return r;
    }
    public void append(int val) {          // store so stored*mult + add == val
        long inv = power(mult, MOD - 2);
        seq[n++] = (val - add % MOD + MOD) % MOD * inv % MOD;
    }
    public void addAll(int inc) { add = (add + inc) % MOD; }
    public void multAll(int m) {
        mult = mult * m % MOD;
        add = add * m % MOD;
    }
    public int getIndex(int idx) {         // rebuild value at idx
        if (idx >= n) return -1;
        return (int)((seq[idx] * mult + add) % MOD);
    }
}

class Fancy {
    static const long long MOD = 1000000007LL;
    vector<long long> seq;
    long long mult = 1, add = 0;

    long long power(long long b, long long e) {   // modular exponentiation
        long long r = 1; b %= MOD;
        while (e > 0) {
            if (e & 1) r = r * b % MOD;
            b = b * b % MOD; e >>= 1;
        }
        return r;
    }
public:
    void append(int val) {                 // store so stored*mult + add == val
        long long inv = power(mult, MOD - 2);
        seq.push_back((val - add % MOD + MOD) % MOD * inv % MOD);
    }
    void addAll(int inc) { add = (add + inc) % MOD; }
    void multAll(int m) {
        mult = mult * m % MOD;
        add = add * m % MOD;
    }
    int getIndex(int idx) {                 // rebuild value at idx
        if (idx >= (int)seq.size()) return -1;
        return (int)((seq[idx] * mult + add) % MOD);
    }
};

Explanation

The naive approach — actually touching every element on addAll and multAll — is O(n) per call, far too slow for 10⁵ mixed operations. The trick is to never modify stored values. Instead we keep a single global affine transform shared by the whole sequence.

Track two numbers: a multiplier mult and an addend add, both starting at mult = 1, add = 0. The current value at any index is defined as stored[i] · mult + add (mod p). Then addAll(inc) is just add += inc, and multAll(m) is mult *= m; add *= m — both O(1), and crucially they distribute over the addend the same way real arithmetic does.

The subtle part is append(val). We must store a normalized number so that applying the current transform reproduces val: we need stored · mult + add ≡ val, so stored = (val − add) · mult⁻¹. Here mult⁻¹ is the modular inverse of mult mod 10⁹+7. Since the modulus is prime, Fermat's little theorem gives mult⁻¹ ≡ mult^p−2, computed by fast exponentiation in O(log p).

Because mult is a product of factors each ≥ 1 and the modulus is prime, mult is never zero mod p, so the inverse always exists. getIndex(idx) simply returns stored[idx] · mult + add (mod p), or -1 if the index is past the end.

Walking Example 1: append 2 with transform (×1, +0) stores 2. addAll 3 sets add = 3. append 7: inverse of mult=1 is 1, so it stores (7−3)·1 = 4. multAll 2: mult = 2, add = 6. getIndex(0) = 2·2 + 6 = 10. ✓ This same lazy-transform idea is what powers lazy propagation in segment trees, which is why the problem lives among tree techniques.

Time: O(log p) per append, O(1) per other op Space: O(n)