# 1622. Fancy Sequence

• Time: Constructor, append(val: int), addAll(inc: int), multAll(m: int), getIndex(idx: int): $O(1)$
• Space: $O(|\texttt{append(val: int)}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 class Fancy { public: // To undo a * val + b and get the original value, we append (val - b) / a. // By Fermat's little theorem: // a^(p - 1) ≡ 1 (mod p) // a^(p - 2) ≡ a^(-1) (mod p) // So, (val - b) / a ≡ (val - b) * a^(p - 2) (mod p) void append(int val) { const long x = (val - b + kMod) % kMod; vals.push_back(x * modPow(a, kMod - 2) % kMod); } // If the value is a * val + b, then the value after adding by inc will be // a * val + b + inc. So, we adjust b to b + inc. void addAll(int inc) { b = (b + inc) % kMod; } // If the value is a * val + b, then the value after multiplying by m will // be a * m * val + b * m. So, we adjust a to a * m and b to b * m. void multAll(int m) { a = (a * m) % kMod; b = (b * m) % kMod; } int getIndex(int idx) { return idx >= vals.size() ? -1 : (a * vals[idx] + b) % kMod; } private: static constexpr int kMod = 1'000'000'007; // For each val in vals, it actually represents a * val + b. vector vals; unsigned long a = 1; unsigned long b = 0; long modPow(long x, long n) { if (n == 0) return 1; if (n % 2 == 1) return x * modPow(x % kMod, (n - 1)) % kMod; return modPow(x * x % kMod, (n / 2)) % kMod; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class Fancy { // To undo a * val + b and get the original value, we append (val - b) / a. // By Fermat's little theorem: // a^(p - 1) ≡ 1 (mod p) // a^(p - 2) ≡ a^(-1) (mod p) // So, (val - b) / a ≡ (val - b) * a^(p - 2) (mod p) public void append(int val) { final long x = (val - b + kMod) % kMod; vals.add(x * modPow(a, kMod - 2) % kMod); } // If the value is a * val + b, then the value after adding by inc will be // a * val + b + inc. So, we adjust b to b + inc. public void addAll(int inc) { b = (b + inc) % kMod; } // If the value is a * val + b, then the value after multiplying by m will // be a * m * val + b * m. So, we adjust a to a * m and b to b * m. public void multAll(int m) { a = (a * m) % kMod; b = (b * m) % kMod; } public int getIndex(int idx) { return idx >= vals.size() ? -1 : (int) ((a * vals.get(idx) + b) % kMod); } private static final int kMod = 1_000_000_007; // For each val in vals, it actually represents a * val + b. private List vals = new ArrayList<>(); private long a = 1; private long b = 0; private int modPow(long x, long n) { if (n == 0) return 1; if (n % 2 == 1) return (int) (x * modPow(x % kMod, (n - 1)) % kMod); return modPow(x * x % kMod, (n / 2)) % kMod; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Fancy: def __init__(self): self.kMod = 1_000_000_007 # For each val in vals, it actually represents a * val + b. self.vals = [] self.a = 1 self.b = 0 # To undo a * val + b and get the original value, we append (val - b) // a. # By Fermat's little theorem: # a^(p - 1) ≡ 1 (mod p) # a^(p - 2) ≡ a^(-1) (mod p) # So, (val - b) / a ≡ (val - b) * a^(p - 2) (mod p) def append(self, val: int) -> None: x = (val - self.b + self.kMod) % self.kMod self.vals.append(x * pow(self.a, self.kMod - 2, self.kMod)) # If the value is a * val + b, then the value after adding by inc will be # a * val + b + inc. So, we adjust b to b + inc. def addAll(self, inc: int) -> None: self.b = (self.b + inc) % self.kMod # If the value is a * val + b, then the value after multiplying by m will # be a * m * val + b * m. So, we adjust a to a * m and b to b * m. def multAll(self, m: int) -> None: self.a = (self.a * m) % self.kMod self.b = (self.b * m) % self.kMod def getIndex(self, idx: int) -> int: return -1 if idx >= len(self.vals) \ else (self.a * self.vals[idx] + self.b) % self.kMod