https://leetcode.com/problems/fancy-sequence/

个人解答

  1. class Fancy:
  3.     def __init__(self):
  4.         self.l = []
  5.         self.k = 1
  6.         self.b = 0
  7.         self.MOD = 10 ** 9 + 7
  10.     def append(self, val: int) -> None:
  11.         self.l.append(((self.MOD + val - self.b) % self.MOD) * pow(self.k, self.MOD - 2, self.MOD) % self.MOD)
  14.     def addAll(self, inc: int) -> None:
  15.         self.b = (self.b + inc % self.MOD) % self.MOD
  18.     def multAll(self, m: int) -> None:
  19.         self.k = (self.k * m % self.MOD) % self.MOD
  20.         self.b = (self.b * m % self.MOD) % self.MOD
  22.     def getIndex(self, idx: int) -> int:
  23.         if idx >= len(self.l):
  24.             return -1
  25.         return ((self.k * self.l[idx]) % self.MOD + self.b) % self.MOD
  29. # Your Fancy object will be instantiated and called as such:
  30. # obj = Fancy()
  31. # obj.append(val)
  32. # obj.addAll(inc)
  33. # obj.multAll(m)
  34. # param_4 = obj.getIndex(idx)

个人思路

没独立做出来

题目分析

参考
https://leetcode.com/problems/fancy-sequence/discuss/898861/C%2B%2B-Math-Solution-O(1)-extra-space-and-O(1)-time-for-each-extra-space-and-O(1)-time-for-each)
https://leetcode.com/problems/fancy-sequence/discuss/898753/Python-Time-O(1)-for-each-for-each)

其实比较容易想到，add和mul两个操作，最终都是对原来数字的一个变换： y = k * x + b ，其中x是原来的数，y是结果。k与b，由append(x)之后的所有操作决定，因此得出这个k和b比较关键。

首先如果单纯通过一系列操作得到k和b比较容易，原表示为kx + b的情况下（如果是初始值，那么k=1, b = 0）附加操作：

  • add(m)：kx + b + m; k’ = k, b’ = b + m
  • mul(m)：(kx + b) * m; k’ = mk, b’ = mb

这样只要每次由操作的时候，根据对应规则更新k和b即可。

但是，关键在于，本题需要获取idx位置的值，而在append这个值的时候，之前已经进行了一定的操作，对于该位置对应的k和b，并不是所有的运算结果，而是自此之后的运算结果，也就是说每个位置对应的k和b并不一定相同。

naive的想法，对于每一个值，都记录属于它的k和b，即：

  • append：初始化该值对应的k和b，k=1，b=0
  • add/mul：对于所有值对应的k与b，按照上述的公式更新

但是这样add/mul的操作是O(n)的，显然不现实

那么其实这里有个很熟悉的思想，类似于prefixSum的味道，比如，求特定位置到数组末尾的和，我们可以用整个sum减去这一位置之前的prefixSum
本题也类似，只不过换成了特定位置到数组末尾的k和b，于是自然地，如果我们记录了整个数组对应的k和b，那么对于第i个数，经过一点小计算可以得出：

  1. k' = k[-1] // k[i] # 抵消掉之前的乘法
  2. b' = b[-1] - b[i] * k' # 抵消掉之前的加法

于是有了初级的代码：

  1. # 错误答案，改动自：https://leetcode.com/problems/fancy-sequence/discuss/898753/Python-Time-O(1)-for-each
  2. class Fancy(object):
  4.     def __init__(self):
  5.         self.A = []
  6.         self.add = [0]
  7.         self.mul = [1]
  9.     def append(self, a):
  10.         self.A.append(a)
  11.         self.add.append(self.add[-1])
  12.         self.mul.append(self.mul[-1])
  14.     def addAll(self, inc):
  15.         self.add[-1] += inc
  17.     def multAll(self, m):
  18.         self.add[-1] = self.add[-1] * m 
  19.         self.mul[-1] = self.mul[-1] * m 
  21.     def getIndex(self, i):
  22.         if i >= len(self.A): return -1
  23.         mod = 10 ** 9 + 7
  24.         m = self.mul[-1] // self.mul[i]
  25.         inc = self.add[-1] - self.add[i] * m
  26.         return (self.A[i] * m + inc) % mod

简洁直观，完美的答案！
然后：Time Limit Exceeded

原因在于，数字累乘会很大，需要每次乘完取模！
但是，如果取模的话，想要抵消掉之前的操作，就不能简单的除和减了，需要求带模的逆，这也是本题比较超出知识范围的一点，费马小定理：
https://zh.wikipedia.org/wiki/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86

  1. x^(m - 1) == 1 (mod m)
  2. x^(-1) == x^(m - 2) (mod m)

如果我们想“除以”k_i以抵消i之前的乘法，那么就乘以它的逆就可以了，本题中， m = 10**9 + 7
于是，经过改动的答案：

  1. # 来源：https://leetcode.com/problems/fancy-sequence/discuss/898753/Python-Time-O(1)-for-each
  2. class Fancy(object):
  4.     def __init__(self):
  5.         self.A = []
  6.         self.add = [0]
  7.         self.mul = [1]
  9.     def append(self, a):
  10.         self.A.append(a)
  11.         self.add.append(self.add[-1])
  12.         self.mul.append(self.mul[-1])
  14.     def addAll(self, inc):
  15.         self.add[-1] += inc
  17.     def multAll(self, m):
  18.         self.add[-1] = self.add[-1] * m % (10 ** 9 + 7)
  19.         self.mul[-1] = self.mul[-1] * m % (10 ** 9 + 7)
  21.     def getIndex(self, i):
  22.         if i >= len(self.A): return -1
  23.         mod = 10 ** 9 + 7
  24.         m = self.mul[-1] * pow(self.mul[i], mod - 2, mod) 
  25.         inc = self.add[-1] - self.add[i] * m
  26.         return (self.A[i] * m + inc) % mod

值得一提，python中的pow，支持第三个参数，对pow的结果取模

其它解法

我最后的解法不是采用上述的方式，稍微有些改动，
上述解法记录了每个对应的prefixSum和prefixMul，但也可以换一个思路（参考自：https://leetcode.com/problems/fancy-sequence/discuss/898861/C%2B%2B-Math-Solution-O(1)-extra-space-and-O(1)-time-for-each-extra-space-and-O(1)-time-for-each)），总是要抵消之前的操作的，为什么不直接对x操作呢！

在每次append(x)的时候，就将其之前的k和b抵消掉，这样直接用最后的k和b作用到修改后的x即可：

  1. x' = (x - b) / k

当然，同样需要遵从取模的减法和除法，看个人解答里的代码就好。