快速幂
快速幂原理：将指数变为二进制，依次右移判断最后一位是否为1。
如果为1则应该将tmp乘到res中。
如果为0，则tmp自己平方，不放入res。
比如：
\[3^{10}=3^{8}*3^{2}=3^{2^3}*3^{2^1}
\]
\]
而10的二进制为1010，二进制从左往右，分别为第0位的（0），第1位的（1），第2位的（0），第3位的（1）。
求数字的幂
/**
* 使用快速幂，求矩阵的幂，矩阵m的p次方
* @param m
* @param p
* @return
*/
public int[][] matrixPower(int[][] m, int p) {
int[][] res = new int[m.length][m[0].length];
for (int i = 0; i < m.length; i++) {
res[i][i] = 1;
}
int[][] tmp = m;
// 快速幂
for (; p != 0; p >>= 1) {
if ((p & 1) != 0) {
res = muliMatrix(res, tmp);
}
tmp = muliMatrix(tmp, tmp);
}
return res;
}
求矩阵的幂
/**
* 使用快速幂，求矩阵的幂，矩阵m的p次方
* @param m
* @param p
* @return
*/
public int[][] matrixPower(int[][] m, int p) {
int[][] res = new int[m.length][m[0].length];
for (int i = 0; i < m.length; i++) {
res[i][i] = 1;
}
int[][] tmp = m;
// 快速幂
for (; p != 0; p >>= 1) {
if ((p & 1) != 0) {
res = muliMatrix(res, tmp);
}
tmp = muliMatrix(tmp, tmp);
}
return res;
}
/**
* 矩阵乘法
* @param m1
* @param m2
* @return
*/
private int[][] muliMatrix(int[][] m1, int[][] m2) {
int[][] res = new int[m1.length][m2[0].length];
for (int i = 0; i < m1.length; i++) {
for (int j = 0; j < m2[0].length; j++) {
for (int k = 0; k < m2.length; k++) {
res[i][j] += m1[i][k] * m2[k][j];
}
}
}
return res;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/195929.html
