鉴于数据规模，直接维护运算结果肯定会超时。问题的关键是怎么使用一种方法能够不即时维护，然后在getIndex的时候也能正确高效返回。这里采用的一种方法是将当前数据表示成 \(val[idx]*mul+add\) 的形式，比如第一个数 \(val_0\) 有 \(val[0]*1+0=val_0\) 那么第一个位置存放的就应该是 \(val[0]=\frac{(val_0-0)}{1}\) (初始时，add=0，mul=1)。这样当前idx的数据就使用当前的mul和add表示了。再分析后续进行mul和add时，如何更新当前的mul和add。对于上一个值 \(val_{idx}=val[idx]*mul+add\) 如果我们要增加add,结果就是\(NewVal_{idx}=val[idx]*mul+(add+\Delta_{add})\)，新的 add 就是 \(add+\Delta_{add}\) ，如果是mul，同理可得应该同时修改 \(new_mul=mul*mul_{new},new_add=add*mul_{new}\)。无论mul和add的执行顺序如何，下一个操作都是在对上一个操作更新后的 \(val[idx]*mul+add\) 进行操作，这保证了无论顺序如何，结果都是正确的。具体写法如下：
MOD=1_000_000_007
class Fancy:def __init__(self):self.data=[]self.add=0self.mul=1def append(self, val: int) -> None:# 除法再摸运算中需要取逆元，取逆元使用费马小定理计算self.data.append((val-self.add)*pow(self.mul,MOD-2,MOD)%MOD)def addAll(self, inc: int) -> None:self.add+=incdef multAll(self, m: int) -> None:self.mul=self.mul*m%MODself.add=self.add*m%MODdef getIndex(self, idx: int) -> int:if idx>=len(self.data):return -1return (self.data[idx]*self.mul+self.add)%MOD