1622-奇妙序列

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

请实现 Fancy 类 ：

• Fancy() 初始化一个空序列对象。
• void append(val) 将整数 val 添加在序列末尾。
• void addAll(inc) 将所有序列中的现有数值都增加 inc 。
• void multAll(m) 将序列中的所有现有数值都乘以整数 m 。
• int getIndex(idx) 得到下标为 idx 处的数值（下标从 0 开始），并将结果对 109 + 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 <= 105
• 总共最多会有 105 次对 append，addAll，multAll 和 getIndex 的调用。

预备知识：乘法逆元

设模数为 m，整数 a 在模 m 的意义下存在乘法逆元整数 a^{-1}~(0 < a^{-1} < m)，当且仅当

a a^{-1} \equiv 1 ~ (\bmod ~ m)

成立。根据上式可得

aa^{-1} = km + 1, \quad k \in \mathbb{N}

整理得

a^{-1} \cdot a - k \cdot m = 1

当 m 为质数时，根据「裴蜀定理」，gcd}(a, m) = 1，因此必存在整数 a^{-1 和 k 使得上式成立。

如果 (a^{-1}_0, k_0) 是一组解，那么

(a^{-1}_0 + cm, k_0 + ca), \quad c \in \mathbb{Z}

都是上式的解。因此必然存在一组解中的整数 a^{-1 满足 0 < a^{-1} < m。

那么如何求出 a^{-1 呢？一种简单的方法是使用「费马小定理」，即

a^{m-1} \equiv 1 ~ (\bmod ~ m)

那么有

a^{m-1} a^{-1} \equiv a^{-1} ~ (\bmod ~ m)

即

a^{m-2} a a^{-1} \equiv a^{-1} ~ (\bmod ~ m)

即

a^{-1} \equiv a^{m-2} ~ (\bmod ~ m)

使用「乘法逆元」有什么好处呢？如果我们要求 \dfrac{c}{a 对 m 取模的结果，那么我们可以化除法为乘法，即

c}{a} \equiv c \cdot a^{-1} ~ (\bmod ~ m)

而 a^{-1 就等于 a^{m-2 对 m 取模的结果，后者使用快速幂即可，时间复杂度为 O(\log m)，可以参考 50. Pow(x, n) 的官方题解 。

方法一：将 getIndex 作为瓶颈

思路与算法

我们可以将所有的 addAll 操作以及 multAll 操作「浓缩」成一次操作 (a, b)，表示将任意整数 x 变为 ax+b：

• 初始时 (a, b) = (1, 0)；

• 遇到 addAll(inc) 操作时，将 b 增加 inc；

• 遇到 multAll(m) 操作时，将 a 和 b 都乘上 m。

我们记 v 为原始序列（也就是保存了每个 append(val) 中 val 的原始值的序列），(a_i, b_i) 表示在 v_i 被加入 v 中之前，所有进行的操作「浓缩」后的结果。特别地，(a_0, b_0) = (1, 0)。当我们遇到 getIndex(idx) 时，考虑 (a_\textit{idx}, b_\textit{idx}) 以及 v 中最后一个元素的 (a, b)：

• 在 v_\textit{idx 被放入 v 之前，操作为 (a_\textit{idx}, b_\textit{idx})；

• 在 v_\textit{idx 被放入 v 之后到目前为止，操作为 (a, b)。

因此，对 v_\textit{idx 进行的操作，就等价于可以将 (a_\textit{idx}, b_\textit{idx}) 变成 (a, b) 的操作，记为 (a_o, b_o)。具体地：

\begin{cases}
a_\textit{idx} \cdot a_o \equiv a ~ (\bmod ~ m) \
b_\textit{idx} \cdot a_o + b_o \equiv b ~ (\bmod ~ m)
\end{cases}

这里 m 为质数 10^9+7。其实就是对于任意的 x，有

a_o ( a_\textit{idx} \cdot x + b_\textit{idx} ) + b_o = ax + b

根据「预备知识」，可以通过乘法逆元得到 a_o

a_o \equiv a_\textit{idx}^{-1} \cdot a ~ (\bmod ~ m)

将其带入也可以得到 b_o

b_o \equiv b - b_\textit{idx} \cdot a_o ~ (\bmod ~ m)

这样返回 a_o \cdot v_\textit{idx} + b_o 对 m 取模的结果即可。

代码

[sol1-C++]

class Fancy {
private:
    static constexpr int mod = 1000000007;
    vector<int> v, a, b;
    
public:
    Fancy() {
        a.push_back(1);
        b.push_back(0);
    }
    
    // 快速幂
    int quickmul(int x, int y) {
        int ret = 1;
        int cur = x;
        while (y) {
            if (y & 1) {
                ret = (long long)ret * cur % mod;
            }
            cur = (long long)cur * cur % mod;
            y >>= 1;
        }
        return ret;
    }
    
    // 乘法逆元
    int inv(int x) {
        return quickmul(x, mod - 2);
    }
    
    void append(int val) {
        v.push_back(val);
        a.push_back(a.back());
        b.push_back(b.back());
    }
    
    void addAll(int inc) {
        b.back() = (b.back() + inc) % mod;
    }
    
    void multAll(int m) {
        a.back() = (long long)a.back() * m % mod;
        b.back() = (long long)b.back() * m % mod;
    }
    
    int getIndex(int idx) {
        if (idx >= v.size()) {
            return -1;
        }
        int ao = (long long)inv(a[idx]) * a.back() % mod;
        int bo = (b.back() - (long long)b[idx] * ao % mod + mod) % mod;
        int ans = ((long long)ao * v[idx] % mod + bo) % mod;
        return ans;
    }
};

复杂度分析

• 时间复杂度：getIndex(idx) 为 O(\log m)，其余均为 O(1)。

• 空间复杂度：O(n)。

方法二：将 append 作为瓶颈

思路与算法

我们也可以将求解逆元的步骤放在 append(val) 操作时。

当我们将 v_i 加入 v 中时，如果目前为止的操作为 (a, b)，那么我们可以将 \dfrac{v-b}{a 代替 v 加入 v_i。这样在任意时刻，所有元素都可以看作进行了相同的操作。

根据「预备知识」，可以通过乘法逆元，计算 (v-b) \cdot a^{-1 来等价 \dfrac{v-b}{a。

代码

[sol2-C++]

class Fancy {
private:
    static constexpr int mod = 1000000007;
    vector<int> v;
    int a, b;
    
public:
    Fancy(): a(1), b(0) {}
    
    // 快速幂
    int quickmul(int x, int y) {
        int ret = 1;
        int cur = x;
        while (y) {
            if (y & 1) {
                ret = (long long)ret * cur % mod;
            }
            cur = (long long)cur * cur % mod;
            y >>= 1;
        }
        return ret;
    }
    
    // 乘法逆元
    int inv(int x) {
        return quickmul(x, mod - 2);
    }
    
    void append(int val) {
        v.push_back((long long)((val - b + mod) % mod) * inv(a) % mod);
    }
    
    void addAll(int inc) {
        b = (b + inc) % mod;
    }
    
    void multAll(int m) {
        a = (long long)a * m % mod;
        b = (long long)b * m % mod;
    }
    
    int getIndex(int idx) {
        if (idx >= v.size()) {
            return -1;
        }
        int ans = ((long long)a * v[idx] % mod + b) % mod;
        return ans;
    }
};

[sol2-Python3]

class Fancy:

    def __init__(self):
        self.mod = 10**9 + 7
        self.v = list()
        self.a = 1
        self.b = 0

    # 快速幂
    def quickmul(self, x: int, y: int) -> int:
        return pow(x, y, self.mod)
    
    # 乘法逆元
    def inv(self, x: int) -> int:
        return self.quickmul(x, self.mod - 2)

    def append(self, val: int) -> None:
        self.v.append((val - self.b) * self.inv(self.a) % self.mod)

    def addAll(self, inc: int) -> None:
        self.b = (self.b + inc) % self.mod

    def multAll(self, m: int) -> None:
        self.a = self.a * m % self.mod
        self.b = self.b * m % self.mod

    def getIndex(self, idx: int) -> int:
        if idx >= len(self.v):
            return -1
        return (self.a * self.v[idx] + self.b) % self.mod

复杂度分析

• 时间复杂度：append(val) 为 O(\log m)，其余均为 O(1)。

• 空间复杂度：O(n)。