1622-奇妙序列(Fancy Sequence)
发表于：2021-12-03 | 分类： 困难
字数统计: 589 | 阅读时长: 3分钟 | 阅读量：

原文链接: https://leetcode-cn.com/problems/fancy-sequence

英文原文

Write an API that generates fancy sequences using the append, addAll, and multAll operations.

Implement the Fancy class:

  • Fancy() Initializes the object with an empty sequence.
  • void append(val) Appends an integer val to the end of the sequence.
  • void addAll(inc) Increments all existing values in the sequence by an integer inc.
  • void multAll(m) Multiplies all existing values in the sequence by an integer m.
  • int getIndex(idx) Gets the current value at index idx (0-indexed) of the sequence modulo 109 + 7. If the index is greater or equal than the length of the sequence, return -1.

 

Example 1:

Input
["Fancy", "append", "addAll", "append", "multAll", "getIndex", "addAll", "append", "multAll", "getIndex", "getIndex", "getIndex"]
[[], [2], [3], [7], [2], [0], [3], [10], [2], [0], [1], [2]]
Output
[null, null, null, null, null, 10, null, null, null, 26, 34, 20]

Explanation
Fancy fancy = new Fancy();
fancy.append(2);   // fancy sequence: [2]
fancy.addAll(3);   // fancy sequence: [2+3] -> [5]
fancy.append(7);   // fancy sequence: [5, 7]
fancy.multAll(2);  // fancy sequence: [5*2, 7*2] -> [10, 14]
fancy.getIndex(0); // return 10
fancy.addAll(3);   // fancy sequence: [10+3, 14+3] -> [13, 17]
fancy.append(10);  // fancy sequence: [13, 17, 10]
fancy.multAll(2);  // fancy sequence: [13*2, 17*2, 10*2] -> [26, 34, 20]
fancy.getIndex(0); // return 26
fancy.getIndex(1); // return 34
fancy.getIndex(2); // return 20

 

Constraints:

  • 1 <= val, inc, m <= 100
  • 0 <= idx <= 105
  • At most 105 calls total will be made to append, addAll, multAll, and getIndex.

中文题目

请你实现三个 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);  // 奇妙序列：[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 <= 105
  • 总共最多会有 105 次对 append，addAll，multAll 和 getIndex 的调用。

通过代码

高赞题解

预备知识：乘法逆元

设模数为 $m$，整数 $a$ 在模 $m$ 的意义下存在乘法逆元整数 $a^{-1}~(0 < a^{-1} < m)$，当且仅当

$$
a a^{-1} \equiv 1 ~ (\bmod ~ m)
$$

成立。根据上式可得

$$
aa^{-1} = km + 1, \quad k \in \mathbb{N}
$$

整理得

$$
a^{-1} \cdot a - k \cdot m = 1
$$

当 $m$ 为质数时，根据「裴蜀定理」，$\text{gcd}(a, m) = 1$，因此必存在整数 $a^{-1}$ 和 $k$ 使得上式成立。

如果 $(a^{-1}_0, k_0)$ 是一组解，那么

$$
(a^{-1}_0 + cm, k_0 + ca), \quad c \in \mathbb{Z}
$$

都是上式的解。因此必然存在一组解中的整数 $a^{-1}$ 满足 $0 < a^{-1} < m$。

那么如何求出 $a^{-1}$ 呢？一种简单的方法是使用「费马小定理」，即

$$
a^{m-1} \equiv 1 ~ (\bmod ~ m)
$$

那么有

$$
a^{m-1} a^{-1} \equiv a^{-1} ~ (\bmod ~ m)
$$

即

$$
a^{m-2} a a^{-1} \equiv a^{-1} ~ (\bmod ~ m)
$$

即

$$
a^{-1} \equiv a^{m-2} ~ (\bmod ~ m)
$$

使用「乘法逆元」有什么好处呢？如果我们要求 $\dfrac{c}{a}$ 对 $m$ 取模的结果，那么我们可以化除法为乘法，即

$$
\frac{c}{a} \equiv c \cdot a^{-1} ~ (\bmod ~ m)
$$

而 $a^{-1}$ 就等于 $a^{m-2}$ 对 $m$ 取模的结果，后者使用快速幂即可，时间复杂度为 $O(\log m)$，可以参考 50. Pow(x, n) 的官方题解。

方法一：将 getIndex 作为瓶颈

思路与算法

我们可以将所有的 addAll 操作以及 multAll 操作「浓缩」成一次操作 $(a, b)$，表示将任意整数 $x$ 变为 $ax+b$：

  • 初始时 $(a, b) = (1, 0)$；

  • 遇到 addAll(inc) 操作时，将 $b$ 增加 $\textit{inc}$；

  • 遇到 multAll(m) 操作时，将 $a$ 和 $b$ 都乘上 $m$。

我们记 $v$ 为原始序列（也就是保存了每个 append(val) 中 val 的原始值的序列），$(a_i, b_i)$ 表示在 $v_i$ 被加入 $v$ 中之前，所有进行的操作「浓缩」后的结果。特别地，$(a_0, b_0) = (1, 0)$。当我们遇到 getIndex(idx) 时，考虑 $(a_\textit{idx}, b_\textit{idx})$ 以及 $v$ 中最后一个元素的 $(a, b)$：

  • 在 $v_\textit{idx}$ 被放入 $v$ 之前，操作为 $(a_\textit{idx}, b_\textit{idx})$；

  • 在 $v_\textit{idx}$ 被放入 $v$ 之后到目前为止，操作为 $(a, b)$。

因此，对 $v_\textit{idx}$ 进行的操作，就等价于可以将 $(a_\textit{idx}, b_\textit{idx})$ 变成 $(a, b)$ 的操作，记为 $(a_o, b_o)$。具体地：

$$
\begin{cases}
a_\textit{idx} \cdot a_o \equiv a ~ (\bmod ~ m) \
b_\textit{idx} \cdot a_o + b_o \equiv b ~ (\bmod ~ m)
\end{cases}
$$

这里 $m$ 为质数 $10^9+7$。其实就是对于任意的 $x$，有

$$
a_o ( a_\textit{idx} \cdot x + b_\textit{idx} ) + b_o = ax + b
$$

根据「预备知识」，可以通过乘法逆元得到 $a_o$

$$
a_o \equiv a_\textit{idx}^{-1} \cdot a ~ (\bmod ~ m)
$$

将其带入也可以得到 $b_o$

$$
b_o \equiv b - b_\textit{idx} \cdot a_o ~ (\bmod ~ m)
$$

这样返回 $a_o \cdot v_\textit{idx} + b_o$ 对 $m$ 取模的结果即可。

代码

[sol1-C++]
class Fancy {
private:
    static constexpr int mod = 1000000007;
    vector<int> v, a, b;
    
public:
    Fancy() {
        a.push_back(1);
        b.push_back(0);
    }
    
    // 快速幂
    int quickmul(int x, int y) {
        int ret = 1;
        int cur = x;
        while (y) {
            if (y & 1) {
                ret = (long long)ret * cur % mod;
            }
            cur = (long long)cur * cur % mod;
            y >>= 1;
        }
        return ret;
    }
    
    // 乘法逆元
    int inv(int x) {
        return quickmul(x, mod - 2);
    }
    
    void append(int val) {
        v.push_back(val);
        a.push_back(a.back());
        b.push_back(b.back());
    }
    
    void addAll(int inc) {
        b.back() = (b.back() + inc) % mod;
    }
    
    void multAll(int m) {
        a.back() = (long long)a.back() * m % mod;
        b.back() = (long long)b.back() * m % mod;
    }
    
    int getIndex(int idx) {
        if (idx >= v.size()) {
            return -1;
        }
        int ao = (long long)inv(a[idx]) * a.back() % mod;
        int bo = (b.back() - (long long)b[idx] * ao % mod + mod) % mod;
        int ans = ((long long)ao * v[idx] % mod + bo) % mod;
        return ans;
    }
};

复杂度分析

  • 时间复杂度：getIndex(idx) 为 $O(\log m)$，其余均为 $O(1)$。

  • 空间复杂度：$O(n)$。

方法二：将 append 作为瓶颈

思路与算法

我们也可以将求解逆元的步骤放在 append(val) 操作时。

当我们将 $v_i$ 加入 $v$ 中时，如果目前为止的操作为 $(a, b)$，那么我们可以将 $\dfrac{v-b}{a}$ 代替 $v$ 加入 $v_i$。这样在任意时刻，所有元素都可以看作进行了相同的操作。

根据「预备知识」，可以通过乘法逆元，计算 $(v-b) \cdot a^{-1}$ 来等价 $\dfrac{v-b}{a}$。

代码

[sol2-C++]
class Fancy {
private:
    static constexpr int mod = 1000000007;
    vector<int> v;
    int a, b;
    
public:
    Fancy(): a(1), b(0) {}
    
    // 快速幂
    int quickmul(int x, int y) {
        int ret = 1;
        int cur = x;
        while (y) {
            if (y & 1) {
                ret = (long long)ret * cur % mod;
            }
            cur = (long long)cur * cur % mod;
            y >>= 1;
        }
        return ret;
    }
    
    // 乘法逆元
    int inv(int x) {
        return quickmul(x, mod - 2);
    }
    
    void append(int val) {
        v.push_back((long long)((val - b + mod) % mod) * inv(a) % mod);
    }
    
    void addAll(int inc) {
        b = (b + inc) % mod;
    }
    
    void multAll(int m) {
        a = (long long)a * m % mod;
        b = (long long)b * m % mod;
    }
    
    int getIndex(int idx) {
        if (idx >= v.size()) {
            return -1;
        }
        int ans = ((long long)a * v[idx] % mod + b) % mod;
        return ans;
    }
};
[sol2-Python3]
class Fancy:

    def __init__(self):
        self.mod = 10**9 + 7
        self.v = list()
        self.a = 1
        self.b = 0

    # 快速幂
    def quickmul(self, x: int, y: int) -> int:
        return pow(x, y, self.mod)
    
    # 乘法逆元
    def inv(self, x: int) -> int:
        return self.quickmul(x, self.mod - 2)

    def append(self, val: int) -> None:
        self.v.append((val - self.b) * self.inv(self.a) % self.mod)

    def addAll(self, inc: int) -> None:
        self.b = (self.b + inc) % self.mod

    def multAll(self, m: int) -> None:
        self.a = self.a * m % self.mod
        self.b = self.b * m % self.mod

    def getIndex(self, idx: int) -> int:
        if idx >= len(self.v):
            return -1
        return (self.a * self.v[idx] + self.b) % self.mod

复杂度分析

  • 时间复杂度：append(val) 为 $O(\log m)$，其余均为 $O(1)$。

  • 空间复杂度：$O(n)$。

统计信息

通过次数 提交次数 AC比率
2767 17869 15.5%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言
设计 数学 线段树
上一篇:
1620-网络信号最好的坐标(Coordinate With Maximum Network Quality)
下一篇:
1608-特殊数组的特征值(Special Array With X Elements Greater Than or Equal X)
本文目录
本文目录
    •
    本站总访问量： 次 |
    Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo