# 倍增

倍增是一种非常重要的思想,在CP中有着丰富的应用。

倍增的本质可以表述为,对于一种操作f(x)f(x),通过计算f(x),f2(x),f4(x),,f2k(x)f(x),f^2(x),f^4(x),\cdots,f^{2^k}(x)来加速求解fn(x)f^n(x)。假设f(x)f(x)的时间复杂度为O(1)O(1),那么直接计算fn(x)f^n(x)的时间复杂度为O(n)O(n),而通过倍增的方法,则可以加速到O(logn)O(\log n)

# 快速幂

快速幂是倍增最常见的应用场景。所谓快速幂,指的是快速求解数xx在模mm意义下的幂xymodmx^y\mod m

# 递归求解

比较直接的想法是递归进行求解。很容易得到下面的递归式:

xy={1y=0(xy2)2y为大于0的偶数(xy12)2xy为大于0的奇数x^y=\left\{\begin{aligned} &1 & y=0 \\ &(x^{\frac{y}{2}})^2 & y\text{为大于0的偶数} \\ &(x^{\frac{y-1}{2}})^2\cdot x & y\text{为大于0的奇数}\end{aligned}\right.

模板题:洛谷P1226 (opens new window)

参考代码(C++)
#include <iostream>

using namespace std;
int fexp(int b, int p, int k) {
  if (p == 0)
    return 1 % k;
  int half = fexp(b, p / 2, k);
  int ans = (long long)half * half % k;
  if (p & 1)
    ans = (long long)ans * b % k;
  return ans;
}

int main() {
  int b, p, k;
  cin >> b >> p >> k;
  cout << b << "^" << p << " mod " << k << "=" << fexp(b, p, k);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

递归方法对于快速幂已经足够,但其缺乏足够的普适性,无法推广到更加一般性的问题。

# 迭代求解

与递归方法相比,迭代方法的思想更加贴近倍增方法的本质。利用xy=xi=0kci2ix^y=x^{\sum_{i=0}^k c_i2^i},我们可以从x1,x2,,x2kx^1,x^2,\cdots,x^{2^k}来计算出xyx^y,而这些数值本身是可以通过反复进行平方运算在O(k)=O(logy)O(k)=O(\log y)的时间内求得的。这里我们需要得到一个非负整数的二进制表示(从低位到高位),只需要不断除以2取余即可。

模板题:洛谷P1226 (opens new window)

参考代码(C++)
#include <iostream>

using namespace std;

int fexp(int b, int p, int k) {
  int ans = 1 % k;
  while (p) {
    if (p & 1)
      ans = (long long)ans * b % k;
    b = (long long)b * b % k;
    p >>= 1;
  }
  return ans % k;
}

int main() {
  int b, p, k;
  cin >> b >> p >> k;
  cout << b << "^" << p << " mod " << k << "=" << fexp(b, p, k);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 倍增思想的推广

# 快速乘

将快速幂中的乘法运算替换为加法运算,我们就可以得到快速乘的算法,也即用O(logn)O(\log n)次加法运算来实现乘nn的操作。

# 矩阵快速幂

将快速幂中的底数改为一个方阵,并将整数乘法改为矩阵乘法,我们就可以得到矩阵快速幂的算法。

# 倍增法求LCA

如果把f(x)f(x)看作是求取xx的父节点,那么fn(x)f^n(x)就可以是看成求取xxnn代的祖先节点。倍增法求LCA的关键就是用倍增方法来快速求取fn(x)f^n(x)

# 稀疏表

稀疏表是一种用于RMQ(区间最值查询)的数据结构。稀疏表的构建同样使用了倍增的思想。