矩阵快速幂

1490111648

矩阵快速幂是用来高效地计算矩阵的高次方的。将次方计算的o（n）的时间复杂度，降到log（n）。

矩阵快速幂原理：
把n个数进行两两分组，比如：XXXXXX 可以转换成 (X*X)(XX)(X*X)

左边是的以X为基础进行的6次运算，右边的是以(X*X)为基础进行了3次计算

所以矩阵快速幂的的好处在于减少重复计算的次数
再来看看矩阵快速幂的具体实现是怎么样的

也是很容易理解

例如
X^21 可以拆分成 (X^16) * (X^4) * (X^1)

X^320 可以拆分成 (X^256) * (X^64)

没错，细心的朋友们肯定是发现了

21 的二级制为 10101，即 2^4 + 2^2 + 2^0 的值 16,4,1

320 的二级制为 101000000，即 2^8 + 2^6 的值 256,64

与二进制快速求幂核心代码一致

long pow(int x, int n){
long p = 1;
while (n != 0){
if (n & 1 == 1) p = x;
x = x;
n >>= 1;
}
return p;
}
完整代码
/

• 矩阵 快速幂

• @author Ape

• /
  public class JuZhen {

  public static int[][] multiply(int[][] a, int[][] b) {

  int[][] array = new int[a.length][b[0].length];
  for (int i = 0; i < a.length; i++) {
      for (int j = 0; j < b[0].length; j++) {
          for (int k = 0; k < a[0].length; k++) {
              array[i][j] += a[i][k] * b[k][j];
          }
      }
  }
  return array;

  }

  public static int[][] pow(int[][] a, int n) {

  int[][] res = new int[a.length][a[0].length];
  for (int i = 0; i < res.length; i++) {
      for (int j = 0; j < res[0].length; j++) {
          if (i == j)
              res[i][j] = 1;
          else
              res[i][j] = 0;
      }
  }
  
  while (n != 0) {
      if ((n & 1) == 1) // 判断最后边一位是否为1
          res = multiply(res, a);
      n >>= 1; // 往右移一位
      a = multiply(a, a);
  }
  return res;

  }

  public static void main(String[] args) {

  int[][] array = { { 1, 1, 1 }, { 1, 1, 1 }, { 1, 1, 1 } };
  int[][] resArray = pow(array, 4);
  for (int i = 0; i < resArray.length; i++) {
      for (int j = 0; j < resArray[0].length; j++) {
          System.out.print(resArray[i][j] + "  ");
      }
      System.out.println();
  }
  System.out.println(2 << 1);

  }

}