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

只有加法

从特殊到一般，先考虑一个简单的问题：只有加法，没有乘法，怎么做？

执行 $\texttt{addAll}(\textit{inc})$ 时，如果把每个数都增加 $\textit{inc}$，就太慢了。

我们可以采用一种「懒更新」的想法，等到调用 $\texttt{getIndex}(\textit{idx})$ 时，才做计算。

比如序列 $\textit{vals} = [3,1,4]$，执行 $\texttt{addAll}(2)$ 时，我们不去把 $\textit{vals}$ 的每个数都增加 $2$，而是用一个变量 $\textit{add}$ 表示「每个数都要增加 $\textit{add}$」。执行 $\texttt{addAll}(2)$ 时，只把 $\textit{add}$ 增加 $2$。等到调用 $\texttt{getIndex}(\textit{idx})$ 时，才计算加法：

$$
\textit{vals}[\textit{idx}] + \textit{add}
$$

即为 $\textit{vals}[\textit{idx}]$ 更新后的数值。

如何处理 $\texttt{append}(\textit{val})$ 呢？

为了让 $\textit{val}$ 兼容 $\textit{vals}[\textit{idx}] + \textit{add}$ 这个式子，我们可以先把 $\textit{val}$ 减少 $\textit{add}$，再添加到 $\textit{vals}$ 的末尾，比如 $\textit{val} = 5$，$\textit{add} = 2$，那么往 $\textit{vals}$ 的末尾添加 $5-2=3$，就可以让式子 $\textit{vals}[\textit{idx}] + \textit{add}$ 对所有元素都保持一致。

只有乘法

如果只有乘法，没有加法呢？

同理，用变量 $\textit{mul}$ 表示「每个数都要乘以 $\textit{mul}$」。执行 $\texttt{multAll}(2)$ 时，只把 $\textit{mul}$ 乘以 $2$。等到调用 $\texttt{getIndex}(\textit{idx})$ 时，才计算乘法：

$$
\textit{vals}[\textit{idx}] \cdot \textit{mul}
$$

即为 $\textit{vals}[\textit{idx}]$ 更新后的数值。

如何处理 $\texttt{append}(\textit{val})$ 呢？

为了让 $\textit{val}$ 兼容 $\textit{vals}[\textit{idx}] \cdot \textit{mul}$ 这个式子，我们可以先把 $\textit{val}$ 除以 $\textit{mul}$，再添加到 $\textit{vals}$ 的末尾，比如 $\textit{val} = 6$，$\textit{mul} = 2$，那么往 $\textit{vals}$ 的末尾添加 $6/2=3$，就可以让式子 $\textit{vals}[\textit{idx}] \cdot \textit{mul}$ 对所有元素都保持一致。

⚠注意：在模运算中，除以 $\textit{mul}$ 等价于乘以 $\textit{mul}$ 关于 $M = 10^9+7$ 的逆元，即 $\textit{mul}^{M-2}$。原理见 模运算的世界：当加减乘除遇上取模。

加法和乘法

把上述方法结合起来，用 $\textit{add}$ 记录操作 $\texttt{addAll}$，用 $\textit{mul}$ 记录操作 $\texttt{multAll}$。

• 初始值：$\textit{add} = 0$，$\textit{mul}=1$。
• 执行 $\texttt{addAll}(\textit{inc})$ 时，把 $\textit{add}$ 增加 $\textit{inc}$。
• 执行 $\texttt{multAll}(m)$ 时，由于 $(v \cdot \textit{mul} + \textit{add})\cdot m = v \cdot (\textit{mul}\cdot m) + \textit{add}\cdot m$，所以把 $\textit{mul}$ 乘以 $m$，把 $\textit{add}$ 乘以 $m$。

调用 $\texttt{getIndex}(\textit{idx})$ 时，计算

$$
\textit{vals}[\textit{idx}] \cdot \textit{mul} + \textit{add}
$$

即为 $\textit{vals}[\textit{idx}]$ 更新后的数值。

如何处理 $\texttt{append}(\textit{val})$ 呢？

为了让 $\textit{val}$ 兼容 $\textit{vals}[\textit{idx}] \cdot \textit{mul} + \textit{add}$ 这个式子，我们可以先计算 $v = \dfrac{\textit{val} - \textit{add}}{\textit{mul}}$，再把 $v$ 添加到 $\textit{vals}$ 的末尾，就可以让式子 $\textit{vals}[\textit{idx}] \cdot \textit{mul} + \textit{add}$ 对所有元素都保持一致。

代码实现时，注意取模。为什么可以在中途取模？原理见 模运算的世界：当加减乘除遇上取模。

###py

MOD = 1_000_000_007

class Fancy:
    def __init__(self):
        self.vals = []
        self.add = 0
        self.mul = 1

    def append(self, val: int) -> None:
        self.vals.append((val - self.add) * pow(self.mul, -1, MOD) % MOD)

    def addAll(self, inc: int) -> None:
        self.add += inc

    def multAll(self, m: int) -> None:
        self.mul = self.mul * m % MOD
        self.add = self.add * m % MOD

    def getIndex(self, idx: int) -> int:
        if idx >= len(self.vals):
            return -1
        return (self.vals[idx] * self.mul + self.add) % MOD

###java

class Fancy {
    private static final int MOD = 1_000_000_007;

    private final List<Integer> vals = new ArrayList<>();
    private long add = 0;
    private long mul = 1;

    public void append(int val) {
        // 注意这里有减法，计算结果可能是负数，+MOD 可以保证计算结果非负
        vals.add((int) ((val - add + MOD) * pow(mul, MOD - 2) % MOD));
    }

    public void addAll(int inc) {
        add = (add + inc) % MOD;
    }

    public void multAll(int m) {
        mul = mul * m % MOD;
        add = add * m % MOD;
    }

    public int getIndex(int idx) {
        if (idx >= vals.size()) {
            return -1;
        }
        return (int) ((vals.get(idx) * mul + add) % MOD);
    }

    private long pow(long x, int n) {
        long res = 1;
        for (; n > 0; n /= 2) {
            if (n % 2 > 0) {
                res = res * x % MOD;
            }
            x = x * x % MOD;
        }
        return res;
    }
}

###cpp

class Fancy {
    static constexpr int MOD = 1'000'000'007;

    vector<int> vals;
    long long add = 0;
    long long mul = 1;

    long long pow(long long x, int n) {
        long long res = 1;
        for (; n; n /= 2) {
            if (n % 2) {
                res = res * x % MOD;
            }
            x = x * x % MOD;
        }
        return res;
    }

public:
    void append(int val) {
        // 注意这里有减法，计算结果可能是负数，+MOD 可以保证计算结果非负
        vals.push_back((val - add + MOD) * pow(mul, MOD - 2) % MOD);
    }

    void addAll(int inc) {
        add = (add + inc) % MOD;
    }

    void multAll(int m) {
        mul = mul * m % MOD;
        add = add * m % MOD;
    }

    int getIndex(int idx) {
        if (idx >= vals.size()) {
            return -1;
        }
        return (vals[idx] * mul + add) % MOD;
    }
};

###go

const mod = 1_000_000_007

func pow(x, n int) int {
res := 1
for ; n > 0; n /= 2 {
if n%2 > 0 {
res = res * x % mod
}
x = x * x % mod
}
return res
}

type Fancy struct {
vals []int
add  int
mul  int
}

func Constructor() Fancy {
return Fancy{mul: 1}
}

func (f *Fancy) Append(val int) {
// 注意这里有减法，计算结果可能是负数，+mod 可以保证计算结果非负
f.vals = append(f.vals, (val-f.add+mod)*pow(f.mul, mod-2)%mod)
}

func (f *Fancy) AddAll(inc int) {
f.add = (f.add + inc) % mod
}

func (f *Fancy) MultAll(m int) {
f.mul = f.mul * m % mod
f.add = f.add * m % mod
}

func (f *Fancy) GetIndex(idx int) int {
if idx >= len(f.vals) {
return -1
}
return (f.vals[idx]*f.mul + f.add) % mod
}

复杂度分析

• 时间复杂度：$\texttt{append}$ 为 $\mathcal{O}(\log M)$，其余为 $\mathcal{O}(1)$，其中 $M=10^9+7$。
• 空间复杂度：$\mathcal{O}(q)$，其中 $q$ 是 $\texttt{append}$ 的调用次数。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

首先，这个问题借助乘法逆元，可以非常优美地解决，具体请参考零神的题解：https://leetcode.cn/problems/fancy-sequence/solution/qi-miao-xu-lie-by-zerotrac2/

经常玩儿算法比赛的同学，还是需要学习乘法逆元的。乘法逆元的在算法竞赛中使用非常广泛，但在面试中近乎没有用。鉴于现在力扣的问题越来越竞赛化，所以学习乘法逆元不吃亏。

---

但是，对于这个问题，如果你不会乘法逆元，也是可以解决的。由于问题的操作都是在一个区间中进行的，所以很容易想到使用线段树求解。

其实树状数组也可以，不过因为力扣官方网站本身有非常好的线段树的解析，所以，这个题解的代码，我使用线段树。

另外值得一提的是，使用线段树解决，其实可以解决这个问题的“更强版本”。在这个问题中，每次操作都是对已经有的所有数据进行的。但是如果问题变成，在指定的某个区间，所有的元素做乘法或者加法，既支持的是 addRange(l, r, inc) 和 multRange(l, r, m) 两种操作的话，线段树也可以轻松应对。（可以出一个“奇妙序列 II”了。）

因为这个问题需要区间更新，所以，需要使用线段树的懒更新功能。强烈建议大家首先仔细阅读学习这份力扣的文档，在这份文档的后续，详细介绍了如何为线段树添加懒更新的功能，并且附有代码：https://leetcode.com/articles/a-recursive-approach-to-segment-trees-range-sum-queries-lazy-propagation/

下面，我对这个问题的解题代码，将直接基于这篇文章的线段树代码进行修改。

---

上面的文章中，解决了如果为指定区间所有元素添加一个值，怎样进行区间更新。但是在这个问题中，还需要处理，如果为指定区间所有元素乘以一个值，要怎么办？

首先，非常关键的一点是，经过一系列题目中的操作，对于每一个元素 x，最终都可以化为 x * a + b 的形式。

比如，对于某个 x，我们有了 ((x + inc1) * m1 + inc2) * m2 + inc3，展开，就有了：

x * (m1 * m2) + (inc1 * m1 * m2 + inc2 * m2 + inc3)。

相当于是 a = m1 * m2；b = inc1 * m1 * m2 + inc2 * m2 + inc3。

因此，我们在线段树的懒标记中，只需要记录经过若干操作以后，对每个元素的 a 是多少，b 是多少，就好了。

所以，我们的线段树需要两个懒标记数组，我使用 lazym 和 lazya，来记录乘数和加数。

下面的关键就是，如果来了一个运算，如何做懒更新？

假设本来的元素是 x，对应的乘数是 a，加数是 b。也就是其实应该是 ax + b。

来了一个乘法运算 m。则变成了 (ax + b) * m = amx + bm。可以看到，乘数和加数都要乘以 m；

来了一个加法运算 inc，则变成了 ax + b + inc = ax + (b + inc)。可以看到，只要加数加 m 就好了。

在下面的代码中，注释有“懒更新”字眼的代码，是实现的这部分逻辑。

除此之外，还有一个问题，懒更新除了更新下面的 lazym 和 lazya 数组，还需要更新当前的区间 tree[treeID]。

这其实很简单，因为当前区间的所有元素都要乘以 a 然后加上 b。所以整体就是对原来的区间和乘以 a，然后加上区间长度 len * b（每个元素都加上了 b）。

在下面的代码中，注释有“区间更新”字眼的代码，是实现的这部分逻辑。

取此之外，所有的逻辑都和上面文章中的线段树是一样的。

参考代码（C++）：

class SegmentTree{

private:
    int n;
    vector<long long> tree, lazya, lazym;
    const long long MOD = 1e9 + 7;

public:
    SegmentTree(int n): n(n), tree(4 * n, 0ll), lazya(4 * n, 0ll), lazym(4 * n, 1ll){}

    void add(int index, int val){
        update(0, 0, n - 1, index, index, val, 1);
    }

    void update_add(int uL, int uR, int inc){
        update(0, 0, n-1, uL, uR, inc, 1);
    }

    void update_mul(int uL, int uR, int mul){
        update(0, 0, n-1, uL, uR, 0, mul);
    }

    int query(int index){
        return query(0, 0, n-1, index);
    }

private:
    void update(int treeID, int treeL, int treeR, int uL, int uR, int inc, int mul){

        if(lazya[treeID] != 0 || lazym[treeID] != 1){
            // 区间更新
            tree[treeID] = (tree[treeID] * lazym[treeID] + (treeR - treeL + 1)* lazya[treeID]) % MOD;

            // 懒更新
            if(treeL != treeR){
                lazym[2 * treeID + 1] = lazym[2 * treeID + 1] * lazym[treeID] % MOD;
                lazya[2 * treeID + 1] = lazya[2 * treeID + 1] * lazym[treeID] % MOD;
                lazya[2 * treeID + 1] = (lazya[2 * treeID + 1] + lazya[treeID]) % MOD;

                lazym[2 * treeID + 2] = lazym[2 * treeID + 2] * lazym[treeID] % MOD;
                lazya[2 * treeID + 2] = lazya[2 * treeID + 2] * lazym[treeID] % MOD;
                lazya[2 * treeID + 2] = (lazya[2 * treeID + 2] + lazya[treeID]) % MOD;
            }
            lazya[treeID] = 0;
            lazym[treeID] = 1;
        }

        if (treeL > uR || treeR < uL) return;

        if(uL <= treeL && uR >= treeR){
            // 区间更新
            tree[treeID] = (tree[treeID] + tree[treeID] * (mul - 1) + (treeR - treeL + 1) * inc) % MOD;

            // 懒更新
            if(treeL != treeR){
                lazym[2 * treeID + 1] = lazym[2 * treeID + 1] * mul % MOD;
                lazya[2 * treeID + 1] = lazya[2 * treeID + 1] * mul % MOD;
                lazya[2 * treeID + 1] = (lazya[2 * treeID + 1] + inc) % MOD;

                lazym[2 * treeID + 2] = lazym[2 * treeID + 2] * mul % MOD;
                lazya[2 * treeID + 2] = lazya[2 * treeID + 2] * mul % MOD;
                lazya[2 * treeID + 2] = (lazya[2 * treeID + 2] + inc) % MOD;
            }
            return;
        }

        int mid = (treeL + treeR) / 2;
        update(2 * treeID + 1, treeL, mid, uL, uR, inc, mul);
        update(2 * treeID + 2, mid + 1, treeR, uL, uR, inc, mul);
        tree[treeID] = (tree[treeID * 2 + 1] + tree[treeID * 2 + 2]) % MOD;
        return;
    }

    int query(int treeID, int treeL, int treeR, int index){

        if(lazya[treeID] != 0 || lazym[treeID] != 1){
            // 区间更新
            tree[treeID] = (tree[treeID] * lazym[treeID] + (treeR - treeL + 1)* lazya[treeID]) % MOD;

            // 懒更新
            if(treeL != treeR){
                lazym[2 * treeID + 1] = lazym[2 * treeID + 1] * lazym[treeID] % MOD;
                lazya[2 * treeID + 1] = lazya[2 * treeID + 1] * lazym[treeID] % MOD;
                lazya[2 * treeID + 1] = (lazya[2 * treeID + 1] + lazya[treeID]) % MOD;

                lazym[2 * treeID + 2] = lazym[2 * treeID + 2] * lazym[treeID] % MOD;
                lazya[2 * treeID + 2] = lazya[2 * treeID + 2] * lazym[treeID] % MOD;
                lazya[2 * treeID + 2] = (lazya[2 * treeID + 2] + lazya[treeID]) % MOD;
            }
            lazya[treeID] = 0;
            lazym[treeID] = 1;
        }

        if(treeL == treeR) return tree[treeID];

        int mid = (treeL + treeR) / 2;
        if(index <= mid) return query(2 * treeID + 1, treeL, mid, index);
        return query(2 * treeID + 2, mid + 1, treeR, index);
    }
};

有了这样一个线段树，题目中要求的 Fancy 类是非常简单的：

class Fancy {

private:
    SegmentTree tree;
    int len = 0;

public:
    Fancy() : tree(1e5 + 1){}

    void append(int val) {
        tree.add(len ++, val);
    }

    void addAll(int inc) {
        tree.update_add(0, len - 1, inc);
    }

    void multAll(int mul) {
        tree.update_mul(0, len - 1, mul);
    }

    int getIndex(int idx) {
        if(idx >= 0 && idx < len)
            return tree.query(idx);
        return -1;
    }
};

对于这个方法，所有的操作都是 O(logn) 的。

依然是，这个方法的优点是，如果问题要求在指定的某个区间做乘法或者加法，即支持的是 addRange(l, r, inc) 和 multRange(l, r, m) 两种操作的话，这个解法也能轻松应对。

---

觉得有帮助请点赞哇！

预备知识：乘法逆元

设模数为 $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$ 取模的结果即可。

代码

###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}$。

代码

###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;
    }
};

###Python

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)$。

一个 「开心字符串」定义为：

• 仅包含小写字母 ['a', 'b', 'c'].
• 对所有在 1 到 s.length - 1 之间的 i ，满足 s[i] != s[i + 1] （字符串的下标从 1 开始）。

比方说，字符串 "abc"，"ac"，"b" 和 "abcbabcbcb" 都是开心字符串，但是 "aa"，"baa" 和 "ababbc" 都不是开心字符串。

给你两个整数 n 和 k ，你需要将长度为 n 的所有开心字符串按字典序排序。

请你返回排序后的第 k 个开心字符串，如果长度为 n 的开心字符串少于 k 个，那么请你返回 空字符串 。

 

示例 1：

输入：n = 1, k = 3
输出："c"
解释：列表 ["a", "b", "c"] 包含了所有长度为 1 的开心字符串。按照字典序排序后第三个字符串为 "c" 。

示例 2：

输入：n = 1, k = 4
输出：""
解释：长度为 1 的开心字符串只有 3 个。

示例 3：

输入：n = 3, k = 9
输出："cab"
解释：长度为 3 的开心字符串总共有 12 个 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"] 。第 9 个字符串为 "cab"

示例 4：

输入：n = 2, k = 7
输出：""

示例 5：

输入：n = 10, k = 100
输出："abacbabacb"

 

提示：

• 1 <= n <= 10
• 1 <= k <= 100

 

首先计算有多少个长为 $n$ 的开心字符串。

这是一个计数问题。有 $n$ 个空位，第一个位置可以填 $3$ 种字母，后面的每个位置，都不能和前一个位置的字母相同，所以都只有 $2$ 种填法，因此方案数为

$$
3\cdot 2^{n-1}
$$

如果 $k > 3\cdot 2^{n-1}$，返回空串。否则答案是存在的。

---

为方便计算，我们先把 $k$ 减一，改成从 $0$ 开始。

以 $n=4$，$k=12=1100_{(2)}$（减一后）为例说明。

答案的第一个字母是什么？

如果第一个字母是 $\texttt{a}$，那么后面的 $n-1=3$ 个位置有 $2^{n-1}=8$ 种填法，不够。

如果第一个字母是 $\texttt{b}$，同样地，后面的 $n-1=3$ 个位置有 $2^{n-1}=8$ 种填法，这就够了，所以答案的第一个字母填 $\texttt{b}$。

现在答案为 $\texttt{b___}$，剩余的三个位置填什么字母？

由于每个位置都有两种填法，这和 $k$ 的二进制可以完美对应，如下表（注意相邻字母不同的要求）：

$k$ 的低三位	对应填法
$000$	$\texttt{aba}$
$001$	$\texttt{abc}$
$010$	$\texttt{aca}$
$011$	$\texttt{acb}$
$100$	$\texttt{cab}$
$101$	$\texttt{cac}$
$110$	$\texttt{cba}$
$111$	$\texttt{cbc}$

对于 $k=1100_{(2)}$（减一后）这个例子，答案是这样填的：

• 答案的第二个字母不能和前一个字母 $\textit{b}$ 相同，只能填 $\texttt{a}$ 或者 $\texttt{c}$，由于 $k$ 这一位是 $1$，所以填 $\texttt{c}$。
• 答案的第三个字母不能和前一个字母 $\textit{c}$ 相同，只能填 $\texttt{a}$ 或者 $\texttt{b}$，由于 $k$ 这一位是 $0$，所以填 $\texttt{a}$。
• 答案的第四个字母不能和前一个字母 $\textit{a}$ 相同，只能填 $\texttt{b}$ 或者 $\texttt{c}$，由于 $k$ 这一位是 $0$，所以填 $\texttt{b}$。

所以答案为 $\texttt{bcab}$。

一般地，答案的第一个字母是第 $\left\lfloor\dfrac{k}{2^{n-1}}\right\rfloor$ 个小写字母，随后的字母可以根据 $k\bmod 2^{n-1}$ 二进制从高到低是 $0$ 还是 $1$，填入相应的字母：

• 首先，如果二进制这一位是 $0$，那么填入 $\texttt{a}$，否则填入 $\texttt{b}$。
• 然后修正：看填入的字母是否大于等于左侧相邻字母，如果大于等于，那么把填入的字母加一。比如左侧相邻字母是 $\texttt{a}$，那么当前这一位如果填的是 $\texttt{a}$，要变成 $\texttt{b}$；如果填的是 $\texttt{b}$，要变成 $\texttt{c}$。

注：这个「加一」的技巧可用于生成两个不同的随机整数，见 961. 在长度 2N 的数组中找出重复 N 次的元素 我的题解的方法四。

###py

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        if k > 3 << (n - 1):
            return ""
        k -= 1  # 改成从 0 开始，方便计算
        ans = [ord('a')] * n
        ans[0] += k >> (n - 1)
        for i in range(1, n):
            ans[i] += k >> (n - 1 - i) & 1
            if ans[i] >= ans[i - 1]:
                ans[i] += 1
        return ''.join(map(chr, ans))

###java

class Solution {
    public String getHappyString(int n, int k) {
        if (k > 3 << (n - 1)) {
            return "";
        }
        k--; // 改成从 0 开始，方便计算
        char[] ans = new char[n];
        ans[0] = (char) ('a' + (k >> (n - 1)));
        for (int i = 1; i < n; i++) {
            ans[i] = (char) ('a' + (k >> (n - 1 - i) & 1));
            if (ans[i] >= ans[i - 1]) {
                ans[i]++;
            }
        }
        return new String(ans);
    }
}

###cpp

class Solution {
public:
    string getHappyString(int n, int k) {
        if (k > 3 << (n - 1)) {
            return "";
        }
        k--; // 改成从 0 开始，方便计算
        string ans(n, 'a');
        ans[0] += k >> (n - 1);
        for (int i = 1; i < n; i++) {
            ans[i] += k >> (n - 1 - i) & 1;
            if (ans[i] >= ans[i - 1]) {
                ans[i]++;
            }
        }
        return ans;
    }
};

###c

char* getHappyString(int n, int k) {
    if (k > 3 << (n - 1)) {
        return "";
    }
    k--; // 改成从 0 开始，方便计算
    char* ans = malloc((n + 1) * sizeof(char));
    ans[0] = 'a' + (k >> (n - 1));
    for (int i = 1; i < n; i++) {
        ans[i] = 'a' + (k >> (n - 1 - i) & 1);
        if (ans[i] >= ans[i - 1]) {
            ans[i]++;
        }
    }
    ans[n] = '\0';
    return ans;
}

###go

func getHappyString(n, k int) string {
if k > 3<<(n-1) {
return ""
}
k-- // 改成从 0 开始，方便计算
ans := make([]byte, n)
ans[0] = 'a' + byte(k>>(n-1))
for i := 1; i < n; i++ {
ans[i] = 'a' + byte(k>>(n-1-i)&1)
if ans[i] >= ans[i-1] {
ans[i]++
}
}
return string(ans)
}

###js

var getHappyString = function(n, k) {
    if (k > 3 << (n - 1)) {
        return "";
    }
    k--; // 改成从 0 开始，方便计算
    const ans = Array(n).fill('a'.charCodeAt(0));
    ans[0] += k >> (n - 1);
    for (let i = 1; i < n; i++) {
        ans[i] += k >> (n - 1 - i) & 1;
        if (ans[i] >= ans[i - 1]) {
            ans[i]++;
        }
    }
    return ans.map(c => String.fromCharCode(c)).join('');
};

###rust

impl Solution {
    pub fn get_happy_string(n: i32, mut k: i32) -> String {
        if k > 3 << (n - 1) {
            return String::new();
        }
        k -= 1; // 改成从 0 开始，方便计算
        let n = n as usize;
        let mut ans = vec![0; n];
        ans[0] = b'a' + (k >> (n - 1)) as u8;
        for i in 1..n {
            ans[i] = b'a' + (k >> (n - 1 - i) & 1) as u8;
            if ans[i] >= ans[i - 1] {
                ans[i] += 1;
            }
        }
        unsafe { String::from_utf8_unchecked(ans) }
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$。
• 空间复杂度：$\mathcal{O}(1)$。返回值不计入。

相似题目

60. 排列序列

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

由题：按字典序画出如下树

由图知，以a开头长度为n的字符串共有$2^{n-1}$种，b,c开头的也是如此，则总计$3*2^{n-1}$种（3棵n层的满二叉树）
若对第n层曲所有树叶结点依次进行编号，从0开始，则第k大的字符串对应序号k-1的节点
由a,b,c开头的字符串均有$2^{n-1}$种，且依次排序
则序号$order/(2^{n-1})$,可以得到其位于哪棵树
则序号$order$%$(2^{n-1})$,可以得到其位于该棵树的第几号节点
得到其在当前树（满二叉树）的位置，则可通过该树分叉出的含义（二进制，0取较小的字符，1去较大的字符）

例如：n=3,k=7

序号6
每棵树叶子结点数:$2^{3-1}=4$
位于6/4=1，位于b开头的树
在b这棵树叶子节点中为6%4=2号节点（0开始）
2对应（n-1)位的二进制为0b10
则字符串为bca

b(起始结点)

->c(上一字符b,当前可选字符a,c。1表示往较大的一个字符转移)

->a(上一字符c,当前可选字符a,b。0表示往较小的一个字符转移)

###java

class Solution {
    public String getHappyString(int n, int k) {
        int count=3<<(n-1);//3*2^(n-1)
        if(k>count) return "";
        char[] result=new char[n];
        int[][] stateTab=new int[][]{{1,2},{0,2},{0,1}};
        //状态0,1,2分别表示a,b,c，
        //转移参数：0表示下一个取较小的字符，1表示下一个取较大的字符
        int order=k-1;//序号k-1,表示第k大
        int index=0 ,state= order>>(n-1);// <=>order/2^(n-1)
        result[index++]=(char)(state+'a');
        int tree=order&((1<<(n-1))-1);//获取其在树中的位置<=>order% 2^(n-1)
        for(int i=n-2;i>=0;i--){
            state=stateTab[state][(tree >> i) & 1];//(tree >> i) & 1取二进制第i位
            result[index++]=(char)(state+'a');
        }
        return String.valueOf(result);
    }
}

1. 该题与字典序第n个10进制数思想一样
2. 整个题解空间就是根节点包含3个子节点，其他非叶节点包含两个子节点（因为相邻的字母不相同）
3. 按照第2步，不断判断当前已确定前缀下，子树的节点数目同目标值大小比较，寻找所在的子树
4. 该方法可以适配解决比如总字符长度到30，k值到1个亿的取值范围

    public String getHappyString(int n, int k) {
        if (total(n) < k) return "";
        char[] result = new char[n];
        int idx = 0;
        while(idx < n) {
            char pre = idx == 0? '0' : result[idx-1];
            result[idx] = pre == 'a' ? 'b' : 'a';
            int len = 1 << (n - idx - 1);
            while(k > len) {
                result[idx] = (char)(result[idx]+1);
                if (result[idx] == pre) {
                    result[idx] = (char)(result[idx]+1);
                }
                k-=len;
            }
            ++idx;
        }
        return new String(result);
    }


    int total(int n) {
        return 3 * (1 << (n-1));
    }

方法一：二分答案

思路与算法

根据题目描述，如果 $t$ 秒可以使山的高度降低到 $0$，那么任何大于 $t$ 的秒数也可以。因此答案具有单调性，我们可以使用二分查找来解决本题。

对于二分查找的每一步，假设当前猜测的秒数为 $\textit{mid}$，我们需要判断所有工人在 $\textit{mid}$ 秒内能否将山的高度降低 $H = \textit{mountainHeight}$。对于第 $i$ 个工人，他将山的高度降低 $k$ 所需的时间为：

$$
\textit{workerTimes}[i] \cdot (1 + 2 + \cdots + k) = \textit{workerTimes}[i] \cdot \frac{k(k+1)}{2}
$$

因此在 $\textit{mid}$ 秒内，第 $i$ 个工人 $i$ 最多能将山降低的高度，是满足

$$\textit{workerTimes}[i] \cdot \frac{k(k+1)}{2} \leq \textit{mid}$$

的最大正整数 $k$。

令 $\textit{work} = \lfloor \dfrac{\textit{mid}}{\textit{workerTimes}[i]} \rfloor$，其中 $\lfloor \cdot \rfloor$ 表示下取整，则需要满足 $\dfrac{k(k+1)}{2} \leq \textit{work}$，利用求一元二次方程求根公式可得：

$$
k = \left\lfloor \frac{-1 + \sqrt{1 + 8 \cdot \textit{work}}}{2} \right\rfloor
$$

我们将所有工人计算得到的 $k$ 值相加，如果总和大于等于 $H$，则说明 $\textit{mid}$ 秒可以完成任务，应当尝试更少的时间，否则尝试更多的时间。

二分查找的下界为 $1$，上界为 $\max(\textit{workerTimes}) \cdot \dfrac{H(H + 1)}{2}$，即最慢的工人独自完成所有工作所需的时间。

代码

###C++

class Solution {
public:
    long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
        int maxWorkerTimes = *max_element(workerTimes.begin(), workerTimes.end());
        long long l = 1, r = static_cast<long long>(maxWorkerTimes) * mountainHeight * (mountainHeight + 1) / 2;
        long long ans = 0;

        while (l <= r) {
            long long mid = (l + r) / 2;
            long long cnt = 0;
            for (int t: workerTimes) {
                long long work = mid / t;
                // 求最大的 k 满足 1+2+...+k <= work
                long long k = (-1.0 + sqrt(1 + work * 8)) / 2 + eps;
                cnt += k;
            }
            if (cnt >= mountainHeight) {
                ans = mid;
                r = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }

        return ans;
    }

private:
    static constexpr double eps = 1e-7;
};

###Python

class Solution:
    def minNumberOfSeconds(self, mountainHeight: int, workerTimes: List[int]) -> int:
        maxWorkerTimes = max(workerTimes)
        l, r, ans = 1, maxWorkerTimes * mountainHeight * (mountainHeight + 1) // 2, 0
        eps = 1e-7
        
        while l <= r:
            mid = (l + r) // 2
            cnt = 0
            for t in workerTimes:
                work = mid // t
                # 求最大的 k 满足 1+2+...+k <= work
                k = int((-1 + ((1 + work * 8) ** 0.5)) / 2 + eps)
                cnt += k
            if cnt >= mountainHeight:
                ans = mid
                r = mid - 1
            else:
                l = mid + 1

        return ans

###Java

class Solution {
    private static final double EPS = 1e-7;
    
    public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
        int maxWorkerTimes = 0;
        for (int t : workerTimes) {
            maxWorkerTimes = Math.max(maxWorkerTimes, t);
        }
        
        long l = 1;
        long r = (long) maxWorkerTimes * mountainHeight * (mountainHeight + 1) / 2;
        long ans = 0;
        
        while (l <= r) {
            long mid = (l + r) / 2;
            long cnt = 0;
            for (int t : workerTimes) {
                long work = mid / t;
                // 求最大的 k 满足 1+2+...+k <= work
                long k = (long)((-1.0 + Math.sqrt(1 + work * 8)) / 2 + EPS);
                cnt += k;
            }
            
            if (cnt >= mountainHeight) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        
        return ans;
    }
}

###C#

class Solution {
    private const double EPS = 1e-7;
    
    public long MinNumberOfSeconds(int mountainHeight, int[] workerTimes) {
        int maxWorkerTimes = 0;
        foreach (int t in workerTimes) {
            maxWorkerTimes = Math.Max(maxWorkerTimes, t);
        }
        
        long l = 1;
        long r = (long)maxWorkerTimes * mountainHeight * (mountainHeight + 1) / 2;
        long ans = 0;
        
        while (l <= r) {
            long mid = (l + r) / 2;
            long cnt = 0;
            
            foreach (int t in workerTimes) {
                long work = mid / t;
                // 求最大的 k 满足 1+2+...+k <= work
                long k = (long)((-1.0 + Math.Sqrt(1 + work * 8)) / 2 + EPS);
                cnt += k;
            }
            
            if (cnt >= mountainHeight) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        
        return ans;
    }
}

###Go

const eps = 1e-7

func minNumberOfSeconds(mountainHeight int, workerTimes []int) int64 {
    maxWorkerTimes := 0
    for _, t := range workerTimes {
        if t > maxWorkerTimes {
            maxWorkerTimes = t
        }
    }
    
    l := int64(1)
    r := int64(maxWorkerTimes) * int64(mountainHeight) * int64(mountainHeight + 1) / 2
    var ans int64 = 0
    
    for l <= r {
        mid := (l + r) / 2
        var cnt int64 = 0
        
        for _, t := range workerTimes {
            work := mid / int64(t)
            // 求最大的 k 满足 1+2+...+k <= work
            k := int64((-1.0 + math.Sqrt(1 + float64(work) * 8)) / 2 + eps)
            cnt += k
        }
        if cnt >= int64(mountainHeight) {
            ans = mid
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    
    return ans
}

###C

#define EPS 1e-7

long long minNumberOfSeconds(int mountainHeight, int* workerTimes, int workerTimesSize) {
    int maxWorkerTimes = 0;
    for (int i = 0; i < workerTimesSize; i++) {
        if (workerTimes[i] > maxWorkerTimes) {
            maxWorkerTimes = workerTimes[i];
        }
    }
    
    long long l = 1;
    long long r = (long long)maxWorkerTimes * mountainHeight * (mountainHeight + 1) / 2;
    long long ans = 0;
    
    while (l <= r) {
        long long mid = (l + r) / 2;
        long long cnt = 0;
        for (int i = 0; i < workerTimesSize; i++) {
            long long work = mid / workerTimes[i];
            // 求最大的 k 满足 1+2+...+k <= work
            long long k = (long long)((-1.0 + sqrt(1 + work * 8)) / 2 + EPS);
            cnt += k;
        }
        
        if (cnt >= mountainHeight) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    
    return ans;
}

###JavaScript

const EPS = 1e-7;

var minNumberOfSeconds = function(mountainHeight, workerTimes) {
    const maxWorkerTimes = Math.max(...workerTimes);
    let l = 1;
    let r = maxWorkerTimes * mountainHeight * (mountainHeight + 1) / 2;
    let ans = 0;
    
    while (l <= r) {
        const mid = Math.floor((l + r) / 2);
        let cnt = 0;
        for (const t of workerTimes) {
            const work = Math.floor(mid / t);
            // 求最大的 k 满足 1+2+...+k <= work
            const k = Math.floor((-1.0 + Math.sqrt(1 + work * 8)) / 2 + EPS);
            cnt += k;
        }
        
        if (cnt >= mountainHeight) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    
    return ans;
}

###TypeScript

const EPS: number = 1e-7;

function minNumberOfSeconds(mountainHeight: number, workerTimes: number[]): number {
    const maxWorkerTimes: number = Math.max(...workerTimes);
    let l: number = 1;
    let r: number = maxWorkerTimes * mountainHeight * (mountainHeight + 1) / 2;
    let ans: number = 0;
    
    while (l <= r) {
        const mid: number = Math.floor((l + r) / 2);
        let cnt: number = 0;
        for (const t of workerTimes) {
            const work: number = Math.floor(mid / t);
            // 求最大的 k 满足 1+2+...+k <= work
            const k: number = Math.floor((-1.0 + Math.sqrt(1 + work * 8)) / 2 + EPS);
            cnt += k;
        }
        
        if (cnt >= mountainHeight) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    
    return ans;
}

###Rust

const EPS: f64 = 1e-7;

impl Solution {
    pub fn min_number_of_seconds(mountain_height: i32, worker_times: Vec<i32>) -> i64 {
        let mountain_height = mountain_height as i64;
        let max_worker_times = *worker_times.iter().max().unwrap_or(&0) as i64;
        
        let mut l: i64 = 1;
        let mut r: i64 = max_worker_times * mountain_height * (mountain_height + 1) / 2;
        let mut ans: i64 = 0;
        
        while l <= r {
            let mid = (l + r) / 2;
            let mut cnt: i64 = 0;
            
            for &t in &worker_times {
                let work = mid / t as i64;
                // 求最大的 k 满足 1+2+...+k <= work
                let k = ((-1.0 + (1.0 + (work as f64) * 8.0).sqrt()) / 2.0 + EPS) as i64;
                cnt += k;
            }
            
            if cnt >= mountain_height {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        
        ans
    }
}

复杂度分析

• 时间复杂度：$O(n \log(MH^2))$，其中 $n$ 是数组 $\textit{workerTimes}$ 的长度，$M$ 是数组 $\textit{workerTimes}$ 中的最大值，$H$ 是 $\textit{mountainHeight}$。二分查找需要 $O(\log(MH^2))$ 次迭代，每次迭代遍历所有工人，需要 $O(n)$ 的时间。

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

给你一个整数 mountainHeight 表示山的高度。

同时给你一个整数数组 workerTimes，表示工人们的工作时间（单位：秒）。

工人们需要 同时 进行工作以 降低 山的高度。对于工人 i :

• 山的高度降低 x，需要花费 workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x 秒。例如：
  • 山的高度降低 1，需要 workerTimes[i] 秒。
  • 山的高度降低 2，需要 workerTimes[i] + workerTimes[i] * 2 秒，依此类推。

返回一个整数，表示工人们使山的高度降低到 0 所需的 最少 秒数。

 

示例 1：

示例 2：

示例 3：

 

提示：

• 1 <= mountainHeight <= 105
• 1 <= workerTimes.length <= 104
• 1 <= workerTimes[i] <= 106

解法：二分

二分答案，并计算每个工人在当前二分的值下能降低多少高度。这个计算也可以通过二分高度来进行。

最差情况是只有一个工人，且 workerTimes[0] = 1e6，所以二分的上界就是 $10^6 \times \frac{(1 + 10^5) \times 10^5}{2} \approx 10^{16}$。

复杂度 $\mathcal{O}(n\log h \log t)$，其中 $h = 10^5$ 是山的高度上限，$t = 10^{16}$ 是二分上限。

参考代码（c++）

###cpp

class Solution {
public:
    long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
        // 通过二分，计算每个工人在 lim 的时间内能降低多少高度
        auto calc = [&](long long lim) {
            int ret = 0;
            for (int t : workerTimes) {
                int head = 0, tail = mountainHeight;
                while (head < tail) {
                    int mid = (head + tail + 1) >> 1;
                    if (1LL * (1 + mid) * mid / 2 * t <= lim) head = mid;
                    else tail = mid - 1;
                }
                ret += head;
                // 提前退出，防止结果溢出
                if (ret >= mountainHeight) break;
            }
            return ret;
        };

        // 二分总用时
        long long head = 1, tail = 1e18;
        while (head < tail) {
            long long mid = (head + tail) >> 1;
            if (calc(mid) >= mountainHeight) tail = mid;
            else head = mid + 1;
        }
        return head;
    }
};

方法一：最小堆模拟

循环 $\textit{mountainHeight}$ 次，每次选一个「工作后总用时」最短的工人，把山的高度降低 $1$。

注意工人们是同时工作的，这个算法不是贪心，是按照事件发生顺序的模拟。

本题视频讲解，欢迎点赞关注~

###py

class Solution:
    def minNumberOfSeconds(self, mountainHeight: int, workerTimes: List[int]) -> int:
        h = [(t, t, t) for t in workerTimes]
        heapify(h)

        for _ in range(mountainHeight):
            # 工作后总用时，当前工作（山高度降低 1）用时，workerTimes[i]
            total, cur, base = h[0]
            heapreplace(h, (total + cur + base, cur + base, base))
        return total  # 最后一个出堆的 total 即为答案

###java

class Solution {
    public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        for (int t : workerTimes) {
            pq.offer(new long[]{t, t, t});
        }

        long ans = 0;
        while (mountainHeight-- > 0) {
            // 工作后总用时，当前工作（山高度降低 1）用时，workerTimes[i]
            long[] top = pq.poll();
            long total = top[0], cur = top[1], base = top[2];
            ans = total; // 最后一个出堆的 total 即为答案
            pq.offer(new long[]{total + cur + base, cur + base, base});
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
        priority_queue<tuple<long long, long long, int>, vector<tuple<long long, long long, int>>, greater<>> pq;
        for (int t : workerTimes) {
            pq.emplace(t, t, t);
        }

        long long ans = 0;
        while (mountainHeight--) {
            // 工作后总用时，当前工作（山高度降低 1）用时，workerTimes[i]
            auto [total, cur, base] = pq.top(); pq.pop();
            ans = total; // 最后一个出堆的 total 即为答案
            pq.emplace(total + cur + base, cur + base, base);
        }
        return ans;
    }
};

###go

func minNumberOfSeconds(mountainHeight int, workerTimes []int) int64 {
h := make(hp, len(workerTimes))
for i, t := range workerTimes {
h[i] = worker{t, t, t}
}
heap.Init(&h)

ans := 0
for range mountainHeight {
ans = h[0].total // 最后一个出堆的 total 即为答案
h[0].cur += h[0].base
h[0].total += h[0].cur
heap.Fix(&h, 0)
}
return int64(ans)
}

// 工作后总用时，当前工作（山高度降低 1）用时，workerTimes[i]
type worker struct{ total, cur, base int }
type hp []worker
func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].total < h[j].total }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (hp) Push(any)             {}
func (hp) Pop() (_ any)         { return }

复杂度分析

• 时间复杂度：$\mathcal{O}(\textit{mountainHeight}\log n)$，其中 $n$ 是 $\textit{workerTimes}$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

方法二：二分答案

由于花的时间越多，能够降低的高度也越多，所以有单调性，可以二分答案。

问题变成：

• 每个工人至多花费 $m$ 秒，总共降低的高度是多少？能否大于等于 $\textit{mountainHeight}$？

遍历 $\textit{workerTimes}$，设 $t=\textit{workerTimes}[i]$，那么有

$$
t + 2t+ \cdots + xt = t\cdot \dfrac{x(x+1)}{2} \le m
$$

即

$$
\dfrac{x(x+1)}{2} \le \left\lfloor\dfrac{m}{t}\right\rfloor = k
$$

解得

$$
x \le \dfrac{-1 + \sqrt{1 + 8k}}{2}
$$

所以第 $i$ 名工人可以把山的高度降低

$$
\left\lfloor \dfrac{-1 + \sqrt{1 + 8k}}{2} \right\rfloor = \left\lfloor \dfrac{-1 + \lfloor\sqrt{1 + 8k}\rfloor}{2} \right\rfloor
$$

上式是个关于下取整的恒等式，理由见 下取整恒等式及其应用。

累加上式，如果和 $\ge \textit{mountainHeight}$，则说明答案 $\le m$，否则说明答案 $> m$。

最后，讨论二分的上下界。这里用开区间二分，其他二分写法也是可以的。

• 开区间二分下界：$0$，无法把山的高度降低到 $0$。
• 开区间二分上界：设 $\textit{maxT}$ 为 $\textit{workerTimes}$ 的最大值，假设每个工人都是最慢的 $\textit{maxT}$，那么单个工人要把山降低 $h=\left\lceil\dfrac{mountainHeight}{n}\right\rceil$，耗时 $\textit{maxT}\cdot(1+2+\cdots+h)=\textit{maxT}\cdot\dfrac{h(h+1)}{2}$，将其作为开区间的二分上界，一定可以把山的高度降低到 $\le 0$。

关于上取整的计算，当 $a$ 和 $b$ 均为正整数时，我们有

$$
\left\lceil\dfrac{a}{b}\right\rceil = \left\lfloor\dfrac{a-1}{b}\right\rfloor + 1
$$

证明见 上取整下取整转换公式的证明。

###py

class Solution:
    def minNumberOfSeconds(self, mountainHeight: int, workerTimes: List[int]) -> int:
        def check(m: int) -> bool:
            left_h = mountainHeight
            for t in workerTimes:
                left_h -= (isqrt(m // t * 8 + 1) - 1) // 2
                if left_h <= 0:
                    return True
            return False

        max_t = max(workerTimes)
        h = (mountainHeight - 1) // len(workerTimes) + 1
        return bisect_left(range(max_t * h * (h + 1) // 2), True, 1, key=check)

###py

class Solution:
    def minNumberOfSeconds(self, mountainHeight: int, workerTimes: List[int]) -> int:
        f = lambda m: sum((isqrt(m // t * 8 + 1) - 1) // 2 for t in workerTimes)
        max_t = max(workerTimes)
        h = (mountainHeight - 1) // len(workerTimes) + 1
        return bisect_left(range(max_t * h * (h + 1) // 2), mountainHeight, 1, key=f)

###java

class Solution {
    public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
        int maxT = 0;
        for (int t : workerTimes) {
            maxT = Math.max(maxT, t);
        }
        int h = (mountainHeight - 1) / workerTimes.length + 1;
        long left = 0;
        long right = (long) maxT * h * (h + 1) / 2;
        while (left + 1 < right) {
            long mid = (left + right) / 2;
            if (check(mid, mountainHeight, workerTimes)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }

    private boolean check(long m, int leftH, int[] workerTimes) {
        for (int t : workerTimes) {
            leftH -= ((int) Math.sqrt(m / t * 8 + 1) - 1) / 2;
            if (leftH <= 0) {
                return true;
            }
        }
        return false;
    }
}

###cpp

class Solution {
public:
    long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
        auto check = [&](long long m) {
            int left_h = mountainHeight;
            for (int t : workerTimes) {
                left_h -= ((int) sqrt(m / t * 8 + 1) - 1) / 2;
                if (left_h <= 0) {
                    return true;
                }
            }
            return false;
        };

        int max_t = ranges::max(workerTimes);
        int h = (mountainHeight - 1) / workerTimes.size() + 1;
        long long left = 0, right = (long long) max_t * h * (h + 1) / 2;
        while (left + 1 < right) {
            long long mid = (left + right) / 2;
            (check(mid) ? right : left) = mid;
        }
        return right;
    }
};

###go

func minNumberOfSeconds(mountainHeight int, workerTimes []int) int64 {
maxT := slices.Max(workerTimes)
h := (mountainHeight-1)/len(workerTimes) + 1
ans := 1 + sort.Search(maxT*h*(h+1)/2-1, func(m int) bool {
m++
leftH := mountainHeight
for _, t := range workerTimes {
leftH -= (int(math.Sqrt(float64(m/t*8+1))) - 1) / 2
if leftH <= 0 {
return true
}
}
return false
})
return int64(ans)
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n\log U)$，其中 $n$ 是 $\textit{workerTimes}$ 的长度，$U\le 5\cdot 10^{10}(10^5+1)$ 是二分上界。二分 $\mathcal{O}(\log U)$ 次，每次 $\mathcal{O}(n)$ 时间。开平方有专门的 CPU 指令，可以视作 $\mathcal{O}(1)$。
• 空间复杂度：$\mathcal{O}(1)$。

专题训练

见下面二分题单的「二分答案：求最小」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

解题思路

纯小白
勿笑

代码

###python3

class Solution:
    def bitwiseComplement(self, N: int) -> int:
        N = bin(N)[2:]
        N = N.replace("0","2")
        N = N.replace("1","0")
        N = N.replace('2','1')
        return int(N,2)

题目让我们把 $n$ 取反。

例如二进制 $n=11001$，取反后是 $00110$，即十进制的 $6$。

看上去，计算 ~n 就好了？

但这样做会把更高位的 $0$ 也取反，对于 $32$ 位整数来说，$11001$ 实际是 $00000000000000000000000000011001$，取反后是 $11111111111111111111111111100110$。

所以对于这个例子，要只把 $n$ 的低 $5$ 位取反，也就是计算 $n$ 和 $11111$ 的异或。

$11111$ 怎么算？设 $w=5$ 是 $n$ 的二进制长度，计算 1 << w 可以得到 $100000$，再减去 $1$，得到 $11111$。

特殊情况：根据题意，$n=0$ 反转后是 $1$，如果用库函数算 $n=0$ 的二进制长度，会算出 $0$，这会导致 $n$ 取反后的值是 $0$。所以特判 $n=0$ 的情况，返回 $1$。

###py

class Solution:
    def bitwiseComplement(self, n: int) -> int:
        if n == 0:
            return 1
        w = n.bit_length()
        return ((1 << w) - 1) ^ n

###java

class Solution {
    public int bitwiseComplement(int n) {
        if (n == 0) {
            return 1;
        }
        int w = 32 - Integer.numberOfLeadingZeros(n);
        return ((1 << w) - 1) ^ n;
    }
}

###cpp

class Solution {
public:
    int bitwiseComplement(int n) {
        if (n == 0) {
            return 1;
        }
        int w = bit_width((uint32_t) n);
        return ((1 << w) - 1) ^ n;
    }
};

###c

int bitwiseComplement(int n) {
    if (n == 0) {
        return 1;
    }
    int w = 32 - __builtin_clz(n);
    return ((1 << w) - 1) ^ n;
}

###go

func bitwiseComplement(n int) int {
if n == 0 {
return 1
}
w := bits.Len(uint(n))
return 1<<w - 1 ^ n
}

###js

var bitwiseComplement = function(n) {
    if (n === 0) {
        return 1;
    }
    const w = 32 - Math.clz32(n);
    return ((1 << w) - 1) ^ n;
};

###rust

impl Solution {
    pub fn bitwise_complement(n: i32) -> i32 {
        if n == 0 {
            return 1;
        }
        let w = n.ilog2() + 1;
        ((1 << w) - 1) ^ n
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(1)$。
• 空间复杂度：$\mathcal{O}(1)$。

专题训练

见下面位运算题单的「一、基础题」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

每个非负整数 N 都有其二进制表示。例如， 5 可以被表示为二进制 "101"，11 可以用二进制 "1011" 表示，依此类推。注意，除 N = 0 外，任何二进制表示中都不含前导零。

二进制的反码表示是将每个 1 改为 0 且每个 0 变为 1。例如，二进制数 "101" 的二进制反码为 "010"。

给你一个十进制数 N，请你返回其二进制表示的反码所对应的十进制整数。

 

示例 1：

输入：5
输出：2
解释：5 的二进制表示为 "101"，其二进制反码为 "010"，也就是十进制中的 2 。

示例 2：

输入：7
输出：0
解释：7 的二进制表示为 "111"，其二进制反码为 "000"，也就是十进制中的 0 。

示例 3：

输入：10
输出：5
解释：10 的二进制表示为 "1010"，其二进制反码为 "0101"，也就是十进制中的 5 。

 

提示：

1. 0 <= N < 10^9
2. 本题与 476：https://leetcode.cn/problems/number-complement/ 相同

拿到题目先不要急，注意观察。

示例1：
输入：5 101
输出：2 010

所以本质是 111（7） - 101（5） = 010（2）

问题转化为：求输入数字N的二进制数长度

求得N的二进制数长度length后，就可以用长为length,各位均为1的数字减去N，即可得到最终结果

由于是二进制，所以可以使用 (int) log2(N) + 1来求其长度

比如5（101）的计算结果为：
(int) log2(N) + 1 = 2 + 1 = 3

而长为length，各位均为1的二进制数字的大小是 2 ^ length - 1
比如111 的大小即为 2^3 - 1 = 7

所以最终结果便是 2 ^ length - 1 - N

###java

class Solution {
    public int bitwiseComplement(int N) {

        //对于0需要单独讨论，因为log(x) 的定义域不包括0
        if(N == 0) return 1;

        //java中没有log2(x)函数，默认log以e为底，log10以10为底
        //所以要用换底公式loga(x) / loga(y) = logy(x)
        //所以loge(N) / loge(2) = log2(N)
        int length = (int)(Math.log(N) / Math.log(2)) + 1;
        
        return (int)(Math.pow(2,  length)) - 1 - N;
    }
}

方法1： 异或运算法

class Solution {
public:
    int bitwiseComplement(int N) {
        
        if(N==0)
            return 1;
        
        int temp1 = 1;
        int temp2 = N;
        
        while(temp2>0){//不停用temp1对原整数进行异或运算，每次运算结束后将temp1朝左移动1位
            
            N ^= temp1;
            temp1 = temp1 << 1;
            temp2 = temp2 >> 1;
        }

        
        return N;
    }
};

方法2： 高位差值法

方法2是看评论学会的，很巧妙～

class Solution {
public:
    int bitwiseComplement(int N) {
        
        int temp = 2;
        
        while(temp<=N){
            
            temp = temp << 1;
        }
        
        return temp - N - 1;
        
    }
};