Skip to content

1622. Fancy Sequence

  • Time:
    • Constructor: $O(1)$
    • append(val: int): $O(1)$
    • addAll(inc: int): $O(1)$
    • multAll(m: int): $O(1)$
    • getIndex(idx: int): $O(1)$
  • Space: $O(|\texttt{append()}|)$
 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<unsigned long> 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<Long> 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)