整数快速幂与矩阵快速幂

前言

公众号菜单栏新增“精选文章”选项，欢迎使用！

一、整数快速幂

顾名思义，快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。

核心思想：求解12^11，等价于求解12 ^ (2 ^ 0 2 ^ 1 2 ^ 3)

代码：

代码语言：javascript复制

typedef long long ll

代码语言：javascript复制

ll fastpow(ll x,ll y) {   //求取x^y 
  ll res=1;
  while(y) {
    if(y % 2==1) { //为奇数，当前最低位为1，res就要乘以当前位置的权重 
      res *= x;
    }
    x *= x;   //每右移一次，最低位的权重都要乘以x 
    y /= 2;   //右移 
  }
  return res;
}

二、矩阵快速幂

矩阵快速幂和整数快速幂的思想一致，只不过答案矩阵的初始状态不再是整数1，而是一个单位矩阵：单位矩阵在矩阵乘法中的作用等同于整数中的1。

定义矩阵：

代码语言：javascript复制

struct matrix {
  ll mat[6][6];
  init() {
    memset(mat, 0, sizeof(mat));
  }
};

定义矩阵乘法：

代码语言：javascript复制

matrix mul(matrix a, matrix b) {   //return a*b
  matrix c;
  c.init();
  for(int i = 0; i < 6; i  ) {
    for(int j = 0; j < 6; j  ) {
      for(int k = 0; k < 6; k  ) {
        c.mat[i][j]  = ((a.mat[i][k] % mod) * (b.mat[k][j] % mod)) % mod;
        c.mat[i][j] %= mod;
      }
    }
  }
  return c;
}

定义矩阵快速幂：

代码语言：javascript复制

matrix fast_pow(matrix A, int n) {   //return A^n % mod
  matrix B;
  B.init();
  for(int i = 0; i < 6; i  ) {   //单位矩阵 
    B.mat[i][i] = 1;
  }
  while(n) {
    if(n & 1) {
      B = mul(B, A);
    }
    A = mul(A, A);
    n >>= 1; 
  }
  return B;
}

公众号

0 人点赞