leetcode 记录
题目：（题号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); // 奇妙序列：[52, 72] -> [10, 14] fancy.getIndex(0); // 返回 10 fancy.addAll(3); // 奇妙序列：[10+3, 14+3] -> [13, 17] fancy.append(10); // 奇妙序列：[13, 17, 10] fancy.multAll(2); // 奇妙序列：[132, 172, 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 的调用。
题解：
class Fancy {
private final long MOD = (long) 1e9 + 7;
private long mul, add;
private List nums;
private List addList, mulList;
public Fancy() {
nums = new ArrayList<>();
addList = new ArrayList<>();
mulList = new ArrayList<>();
mul = 1;
add = 0;
}
public void append(int val) {
nums.add(val);
addList.add(add);
mulList.add(mul);
}
public void addAll(int inc) {
add = (add + inc) % MOD;
}
public void multAll(int m) {
add = (add * m) % MOD;
mul = (mul * m) % MOD;
}
public int getIndex(int idx) {
if (idx >= nums.size()) return -1;
long ans = nums.get(idx);
long q = qpow(mulList.get(idx), MOD - 2L);
ans = ans * mul % MOD;
ans = ans * q % MOD;
ans = (ans + add) % MOD;
ans = (ans - addList.get(idx) * mul % MOD * q % MOD + MOD) % MOD;
return (int) ans;
}
private long qpow(long a, long p) {
long ans = 1;
while (p > 0) {
if ((p & 1) > 0) ans = ans * a % MOD;
a = a * a % MOD;
p >>= 1;
}
return ans;
}
}腾讯云开发者
