题目描述

请你实现三个 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 的调用。

算法分析

对于某一个V，可能会进行某些操作 $((V + A1) * M1 + A2 + A3) * M2 * M3$，将其化简等价于

• $V * M + A$
• $M = M1 * M2 * M3$
• $A = A1 * M1 * M2 * M3 + (A2 + A3) * M2 * M3$

1、加和乘操作
$V * M + A$
初始 $M = 1, A = 0$

• 当进来了一个数，需要给该数记录从当前位置的M和A
• 当对所有数进行加操作时+ P : A += P
• 当对所有数进行乘操作时* p : M *= P, A *= P

2、得到下标为 $idx$ 处的数值

假设 $idx$ 位置的 $M$ 是 $M2$ , $A$ 是 $A2$，当前的 $M$ 是 $M1$，$A$ 是 $A1$，则该值是 $V * \frac{M2}{M1} + (A2 - A1 * \frac{M2}{M1})$ ，这里是除以 $M$ 再取模，等价于 乘 $M$ 的逆元再取模

时间复杂度

查询$O(log $ $mod)$，其他$O(1)$

参考文献

参考 喂你脚下有坑的视频

Java 代码

class Fancy {
    static List<Long> nums = new ArrayList<Long>();
    static List<Long> mulArr = new ArrayList<Long>();
    static List<Long> addArr = new ArrayList<Long>();
    static int mod = 1000000000 + 7;
    static long M, A;
    static long qmi(long a, long k, long p)
    {
        long res = 1 % p;
        while(k != 0)
        {
            if((k & 1) == 1) res = res * a % p;
            k >>= 1;
            a = a * a % p;
        }
        return res;
    }
    public Fancy() {
        nums.clear();
        mulArr.clear();
        addArr.clear();
        M = 1;
        A = 0;
    }

    public void append(int val) {
        nums.add((long) val);
        mulArr.add(M);
        addArr.add(A);
    }

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

    public void multAll(int m) {
        M = M * m % mod;
        A = A * m % mod;
    }

    public int getIndex(int idx) {
        if(idx >= nums.size()) return -1;
        long V = nums.get(idx);
        long Mt = mulArr.get(idx), At = addArr.get(idx);
        return (int)((V * M % mod * qmi(Mt, mod - 2, mod) % mod + A % mod - At * M % mod * qmi(Mt, mod - 2, mod) % mod + mod) % 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);
 */