本文涉及知识点
设计 数学
LeetCode1622. 奇妙序列
请你实现三个 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 的调用。
数学
已经增加了n个数，令第i个数是x[i]，x∈ \in∈[0,n)。
乘法m次。令第i个乘法的m为mml[i]，它们的积为mmm[i]=mm[i]*mm[i+1] ⋯ \cdots⋯mm[m-1]。
mm[0]之前的所有加法参数inc之和为sumInc[0]。mm[i]和mm[i+1]之间的inc和为suninc[i]，mm[m-1]之h后的和为suminc[m]。
此时，第i个数可以表示为：
a× \times×val[i]+b。如果此时乘以m，就变成了amval[i]+mb。如果此时增加inc。就变成了a× \times×val[i]+b+inc。
我们只需要记录系数(a,b)。
如果我们不能统一各数的系数(a,b)，那每mul或all一次的时间复杂度是O(n)，总时间复杂度是O(nn)，超时。
除以 mmm[t] 就 是第i个数刚加入b(0)。mmm[t] = mmm[n-1]/ 加入第i个数的a(0)。
m_va[i] 记录第i个数加入时的a(0),m_vb[i]记录第i个数加入时b(0)。
b(i)等于 = b(0)-m_vb[i]*(mmm[m-1]/m_va[i])
代码
核心代码
template<int MOD = 1000000007> class C1097Int { public: C1097Int(long long llData = 0) :m_iData(llData% MOD) { } C1097Int operator+(const C1097Int& o)const { return C1097Int(((long long)m_iData + o.m_iData) % MOD); } C1097Int& operator+=(const C1097Int& o) { m_iData = ((long long)m_iData + o.m_iData) % MOD; return *this; } C1097Int& operator-=(const C1097Int& o) { m_iData = (m_iData + MOD - o.m_iData) % MOD; return *this; } C1097Int operator-(const C1097Int& o) { return C1097Int((m_iData + MOD - o.m_iData) % MOD); } C1097Int operator*(const C1097Int& o)const { return((long long)m_iData * o.m_iData) % MOD; } C1097Int& operator*=(const C1097Int& o) { m_iData = ((long long)m_iData * o.m_iData) % MOD; return *this; } bool operator<(const C1097Int& o)const { return m_iData < o.m_iData; } C1097Int pow(long long n)const { C1097Int iRet = 1, iCur = *this; while (n) { if (n & 1) { iRet *= iCur; } iCur *= iCur; n >>= 1; } return iRet; } C1097Int PowNegative1()const { return pow(MOD - 2); } int ToInt()const { return m_iData; } private: int m_iData = 0;; }; class Fancy { public: Fancy() { } void append(int val) { m_va.emplace_back(m_a); m_vb.emplace_back(m_b); m_val.emplace_back(val); } void addAll(int inc) { m_b += inc; } void multAll(int m) { m_a *= m; m_b *= m; } int getIndex(int idx) { if (idx >= m_val.size()) { return -1; } C1097Int<> biB = m_b - m_vb[idx] * (m_a * m_va[idx].PowNegative1()); C1097Int<> biRet = m_val[idx] * m_a * m_va[idx].PowNegative1() + biB; return biRet.ToInt(); } C1097Int<> m_a = 1, m_b = 0; vector<C1097Int<>> m_va, m_vb,m_val; };
2023年8月
class Fancy { public: Fancy() { } void append(int val) { C1097Int<> tmp(val); tmp -= m_iAdd * m_iMul; tmp *= m_iMul.PowNegative1(); m_vValue.emplace_back(tmp); } void addAll(int inc) { m_iAdd *= m_iMul; m_iAdd += inc; m_iAdd *= m_iMul.PowNegative1(); } void multAll(int m) { m_iMul *= m; } int getIndex(int idx) { if (idx >= m_vValue.size()) { return -1; } return ((m_vValue[idx] + m_iAdd) * m_iMul).ToInt(); } vector<C1097Int<>> m_vValue; C1097Int<> m_iMul = 1; C1097Int<> m_iAdd = 0; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
