之前做题目喷到一题，自己通过递归求解也能做出来，但是数据量一大超过10000，就基本上凉凉了，所以自己之后一直看了别人的解法，认识到了矩阵快速幂的好处，自己之前也碰到过，但是只是简单了解了一下，所以什么东西最好还是精一点的好，略懂是不行的。 首先一般的幂运算，普通的解法就是一次乘，比如说X^12，可能就是简单的12个X相乘，总共计算的c次数就是12次，但是我们可以把12分解成12=4 8，那么只需要计算4次方以及8次方，这样我们一次计算2次方，4次方，8次方，最后直接将4次方与8次方相乘即可，那这样我们最后只计算了4次，次数大大的减少了，所以非常实用。 同理我们也可以将这种运算方式运用到矩阵上。 下面就是详细的代码：
代码语言：javascript复制import java.util.Scanner;
public class Main {
public static int [][] figure(int [][]num1,int [][]num2)//矩阵乘法函数
{
int [][]num3=new int [num1.length][num2[0].length];
for(int i=0;i<num1.length;i )
{
for(int j=0;j<num2[0].length;j )
{
for(int k=0;k<num1[0].length;k )
{
num3[i][j] =num1[i][k]*num2[k][j];
}
}
}
return num3;
}
public static int [][]figure1(int [][]num1,int n)矩阵的n次方函数
{
int [][]num2=new int [num1[0].length][num1[0].length];//构造单位矩阵
for(int i=0;i<num1.length;i )
{
num1[i][i]=1;
}
int [][]res=new int [num1.length][num1[0].length];
while(n>0)
{
if((n&1)==1) res=figure(num1, num2);
num1=figure(num1, num1);
n>>=1;
}
return res;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int k=sc.nextInt();
int [][]num1=new int [n][m];
int [][]num2=new int [m][k];
for(int i=0;i<n;i )
{
for(int j=0;j<m;j )
{
num1[i][j]=sc.nextInt();
}
}
for(int i=0;i<m;i )
{
for(int j=0;j<k;j )
{
num2[i][j]=sc.nextInt();
}
}
int [][]num3=figure(num1, num2);
int [][]num4=figure1(num3, 4);
}
}通常情况下矩阵快速幂不会单独使用，一般都是与动态规划一同使用，毕竟矩阵快速幂中的矩阵就类似于状态方程。 作者很菜，如有不足，请大佬指出。
