【设计】 【数学】1622 奇妙序列

本文涉及知识点

设计 数学

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 <= 10⁵
总共最多会有 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)，超时。

第0个数的a，权且记作a(0)=mmm[0]。
$$b(0)=sumInc[0]\times mmm[0]+sumInc[1]\times mmm[1]\cdots sumInc[m-1]\times mmm[m-1]+\ast \ast sumInc[m]\ast \ast$$

假定第i个数前面有t个乘法,第i个数和它前面的乘号之间的inc之和ti，乘法之和tm：
$$b(i)=(sumInc[t]-ti)\times mmm[t]+sumInc[t+1]\times mmm[t+1]\cdots summInc[m-1]\times mmm[m-1]+\ast \ast sumInc[m]\ast \ast$$
$$b(0)-b(i)=sumInc[0]\times mmm[0]+sumInc[1]\times mmm[1]\cdots suminc[t-1]\times mmm[t-1]+ti\times mmm[t]$$
除以 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++**实现。