快速幂（二分，结合律）

一般的快速幂，计算(a^b)%c

从朴素的O(n)到O(lg n)。

基本思路：把b看做二进制。底数a反复平方（存下来），迭代or递归。

计算5^122 = 5^(1111010)B = 5^64 * 5^32 * 5^16 * 5^8 * 5^2

• 迭代

  //calculate a^b mod p
  int fastPow_iterative(int a, int b, int p) {
      int res = 1;
      while (b) {
          if (b & 1) res = a * 1ll * res % p;
          a = a * 1ll * a % p;
          b >>= 1;
      }
      return res;
  }
  

• 递归

  int fastPow_recursive(int a, int b, int p) {
      if (b == 0) return 1;
      if (b & 1) { // odd
          return fastPow_recursive(a, b-1, p) * a % p;
      } else { // even
          int temp = fastPow_recursive(a, b >> 1, p);
          return temp * 1ll * temp % p;
      }
  }
  

矩阵快速幂

在递推（动态规划）的应用：LeetCode70 爬楼梯，题虽简单，官方题解很精彩。

注意矩阵的构造。

const int MATRIX_SIZE = 2;
struct Matrix {
  int arr[MATRIX_SIZE][MATRIX_SIZE];
  Matrix() {
    memset(arr, 0, sizeof(arr));
  }
  
  // init as E
  void unit() {
    for(int i = 0; i < MATRIX_SIZE; i++) arr[i][i] = 1;
  }
  
  // Overload op *
  // const A(this), const B
  Matrix operator*(const Matrix &B) const{
    Matrix ans;
    for(int i = 0; i < MATRIX_SIZE; i++) {
      for(int j = 0; j < MATRIX_SIZE; j++) {
        for(int k = 0; k < MATRIX_SIZE; k++) {
          ans[i][j] += arr[i][k]*B.arr[k][j];
        }
      }
    }
    return ans;
  }
  
  Matrix operator^(int n) const{
    Matrix ans;
    ans.unit(); // ans = E
    Matrix A = *this;
    while(n) {
        if (n & 1) ans = ans * A;
        A = A * A;
        n >>= 1;
    }
  }
};