题目描述

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

请实现 Fancy 类：

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

算法

(数学) 插入 $O(\log mod)$；其他 $O(1)$

1. 如果只有加法操作存在，则我们可以直接记录一个常量 add 表示当前已经累加的值。每次加入新数字 val 时，将 val 减去 add。
2. 如果只有乘法操作存在，同理记录常量 mul。但加入新数字时，需要将 val 除以 mul，除法操作可以在同余意义下看做 乘法逆元。由于 10^9 + 7 是质数，根据 费马小定理，mul ^ (mod - 1) 与 1 在模 mod 下同余，则 mul 的乘法逆元为 mul ^ (mod - 2) 模 mod。
3. 如果加法和乘法同时存在，则需要同时记录 add 和 mul，同时加 inc 时，add = add + inc；同时乘 m 时，需要让 mul = mul * m 且 add = add + inc，这是因为乘法的优先级高于加法。加入新数字时，令 val = val - add，然后再令 val = val * (mul ^ (mod - 2))。查询时，返回 nums[idx] * mul + add。

时间复杂度

• 插入操作需要求乘法逆元，通过快速幂的时间复杂度为 $O(\log mod)$。
• 其他操作的时间复杂度显然为常数。

空间复杂度

• 需要 $O(n)$ 的空间记录数组。

C++ 代码

#define LL long long

class Fancy {
private:
    vector<LL> nums;
    LL add, mul;
    const int mod = 1000000007;

    LL power(LL x, int y) {
        LL tot = 1, p = x;
        for (; y; y >>= 1) {
            if (y & 1)
                tot = (tot * p) % mod;
            p = (p * p) % mod;
        }
        return tot;
    }

public:
    Fancy() {
        add = 0;
        mul = 1;
    }

    void append(int val) {
        val = ((val - add) % mod + mod) % mod;
        val = (val * power(mul, mod - 2)) % mod;
        nums.push_back(val);
    }

    void addAll(int inc) {
        add = (add + inc) % mod;
    }

    void multAll(int m) {
        add = add * m % mod;
        mul = mul * m % mod;
    }

    int getIndex(int idx) {
        if (idx >= nums.size())
            return -1;
        return (nums[idx] * mul + add) % mod;
    }
};

/**
 * Your Fancy object will be instantiated and called as such:
 * Fancy* obj = new Fancy();
 * obj->append(val);
 * obj->addAll(inc);
 * obj->multAll(m);
 * int param_4 = obj->getIndex(idx);
 */