奇妙序列

难度: Hard

请你实现三个 API append，addAll 和 multAll 来实现奇妙序列。

请实现 Fancy 类：

Fancy() 初始化一个空序列对象。
void append(val) 将整数 val 添加在序列末尾。
void addAll(inc) 将所有序列中的现有数值都增加 inc 。
void multAll(m) 将序列中的所有现有数值都乘以整数 m 。
int getIndex(idx) 得到下标为 idx 处的数值（下标从 0 开始），并将结果对 10⁹ + 7 取余。如果下标大于等于序列的长度，请返回 -1 。

示例：

输入：
["Fancy", "append", "addAll", "append", "multAll", "getIndex", "addAll", "append", "multAll", "getIndex", "getIndex", "getIndex"]
[[], [2], [3], [7], [2], [0], [3], [10], [2], [0], [1], [2]]
输出：
[null, null, null, null, null, 10, null, null, null, 26, 34, 20]

解释：
Fancy fancy = new Fancy();
fancy.append(2);   // 奇妙序列：[2]
fancy.addAll(3);   // 奇妙序列：[2+3] -> [5]
fancy.append(7);   // 奇妙序列：[5, 7]
fancy.multAll(2);  // 奇妙序列：[5*2, 7*2] -> [10, 14]
fancy.getIndex(0); // 返回 10
fancy.addAll(3);   // 奇妙序列：[10+3, 14+3] -> [13, 17]
fancy.append(10);  // 奇妙序列：[13, 17, 10]
fancy.multAll(2);  // 奇妙序列：[13*2, 17*2, 10*2] -> [26, 34, 20]
fancy.getIndex(0); // 返回 26
fancy.getIndex(1); // 返回 34
fancy.getIndex(2); // 返回 20

提示：

1 <= val, inc, m <= 100
0 <= idx <= 10⁵
总共最多会有 10⁵ 次对 append，addAll，multAll 和 getIndex 的调用。

Submission

运行时间: 436 ms

内存: 53.9 MB

MOD  = 10**9 + 7
class Fancy:
    def __init__(self):
        self.k = [1] #用于保存一次项系数
        self.b = [0] #保存常数项
        self.nums = [] #插入的数
        self.f_idx = []   

    def append(self, val: int) -> None:
        self.nums.append(val)  
        self.f_idx.append(len(self.k) - 1) #记录插入新数的时间，从而确定求哪个反函数

    def addAll(self, inc: int) -> None:
        self.k.append( self.k[-1] )  #维护线性函数系数
        self.b.append( ( self.b[-1]+inc )% MOD ) 

    def multAll(self, m: int) -> None:
        self.k.append( ( self.k[-1]*m )% MOD ) #维护线性函数系数
        self.b.append( ( self.b[-1]*m )% MOD )  

    def getIndex(self, idx: int) -> int:
        if idx >= len(self.nums):return -1
        func_index = self.f_idx[idx] 
        one_over_k =  pow( self.k[func_index], -1,MOD) #求倒数，即反函数的一次项
        return ( self.k[-1]  * one_over_k*( self.nums[idx] -  self.b[func_index] ) + self.b[-1] ) % MOD #求出最终函数并直接计算

Explain

这个题解利用线性变换的组合来避免对序列每个元素逐一进行操作，从而提高效率。每次添加或乘法操作时，我们不直接更新序列，而是记录当前操作的一次项系数和常数项，并将其与之前的操作合并。当调用getIndex时，我们使用保存的操作状态和反函数来计算具体位置的数值。这种方法把对整个序列的操作压缩为对两个参数（一次项系数和常数项）的操作，大大降低了处理时间。

时间复杂度: O(1) per operation

空间复杂度: O(n)

MOD  = 10**9 + 7
class Fancy:
    def __init__(self):
        self.k = [1] # 保存一次项系数
        self.b = [0] # 保存常数项
        self.nums = [] # 插入的数
        self.f_idx = [] # 记录每个数对应的函数版本索引

    def append(self, val: int) -> None:
        self.nums.append(val)
        self.f_idx.append(len(self.k) - 1) # 记录插入时对应的操作版本

    def addAll(self, inc: int) -> None:
        self.k.append(self.k[-1]) # 继承上一次的一次项系数
        self.b.append((self.b[-1] + inc) % MOD) # 更新常数项，取模

    def multAll(self, m: int) -> None:
        self.k.append((self.k[-1] * m) % MOD) # 更新一次项系数，取模
        self.b.append((self.b[-1] * m) % MOD) # 更新常数项，取模

    def getIndex(self, idx: int) -> int:
        if idx >= len(self.nums): return -1 # 超出索引范围返回-1
        func_index = self.f_idx[idx] # 获取该元素的函数版本索引
        one_over_k = pow(self.k[func_index], -1, MOD) # 使用费马小定理计算反函数的一次项
        return (self.k[-1] * one_over_k * (self.nums[idx] - self.b[func_index]) + self.b[-1]) % MOD # 计算并返回结果

Explore

`k`和`b`数组在`Fancy`类中用于存储每次操作后序列的线性变换参数。具体来说，`k`数组存储的是每次操作后的一次项系数，而`b`数组存储的是常数项。这两个数组的每个元素对应一次操作的状态，反映了从初始状态到当前状态的所有线性变换的累积效果。每当进行添加或乘法操作时，`k`和`b`都会添加新的元素，这些元素基于前一次的值进行计算，从而记录了操作的历史并使得之后的任何时间点都能追溯到任何先前的状态。

在`addAll`和`multAll`方法中更新`k`和`b`时需要取模运算主要是为了防止数值溢出，并确保所有计算都在一个可控的数值范围内进行。这里的模数`MOD`为`10**9 + 7`，一个常用的大质数，可以有效减少由于大数运算带来的性能问题和精度问题。取模运算也有利于保持结果的一致性和可预测性，特别是在面对大量操作和大数据量的情况下。

在`getIndex`方法中，需要计算`one_over_k`作为当前一次项系数的逆元，以便能够将累积的线性变换逆向应用到具体的序列值上。费马小定理指出，如果`p`是一个质数且`a`是一个不被`p`整除的整数，则`a^(p-1) ≡ 1 (mod p)`。由此可得`a^(p-2) ≡ a^(-1) (mod p)`。在这里，`MOD`是质数，所以可以使用费马小定理来计算`k`的逆元`one_over_k`，即`one_over_k = pow(k, MOD-2, MOD)`。这个逆元使得我们可以解除之前所有乘法操作的影响，从而正确地计算出原始值。

在`getIndex`方法中，为了确保最终结果的正确性，方法首先找到元素的初始插入时对应的操作版本索引`func_index`。这个索引帮助我们定位到元素被插入时的`k`和`b`的值。然后通过计算从那个时间点到当前的所有操作的累积效应，使用当前的`k`和`b`值以及之前保存的那些值，通过反函数来取消之前的变换，最终得到正确的元素值。这种方法确保了无论多少次操作，每次请求的复杂度都被限制在常数时间内，同时保证了操作的正确性。