之前做题目喷到一题，自己通过递归求解也能做出来，但是数据量一大超过10000，就基本上凉凉了，所以自己之后一直看了别人的解法，认识到了矩阵快速幂的好处，自己之前也碰到过，但是只是简单了解了一下，所以什么东西最好还是精一点的好，略懂是不行的。
首先一般的幂运算，普通的解法就是一次乘，比如说X^12，可能就是简单的12个X相乘，总共计算的c次数就是12次，但是我们可以把12分解成12=4+8，那么只需要计算4次方以及8次方，这样我们一次计算2次方，4次方，8次方，最后直接将4次方与8次方相乘即可，那这样我们最后只计算了4次，次数大大的减少了，所以非常实用。
同理我们也可以将这种运算方式运用到矩阵上。
下面就是详细的代码：
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); } }
通常情况下矩阵快速幂不会单独使用，一般都是与动态规划一同使用，毕竟矩阵快速幂中的矩阵就类似于状态方程。
作者很菜，如有不足，请大佬指出。
