题解 | 矩阵幂

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n,k;
	while(cin>>n>>k) {
		int a[n][n],b[n][n];
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				cin>>a[i][j];
				b[i][j] = i==j?1:0;
			}
		}
		while(k!=0) {
			int tmp[n][n];
			if(k%2==1) {
				for(int i=0; i<n; i++) {
					for(int j=0; j<n; j++) {
						tmp[i][j]=0;
						for(int k=0; k<n; k++) {
							tmp[i][j]+=b[i][k]*a[k][j];
						}
					}
				}
				for(int i=0; i<n; i++) {
					for(int j=0; j<n; j++) {
						b[i][j]=tmp[i][j];
					}
				}

			}
			k/=2;
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
					tmp[i][j]=0;
					for(int k=0; k<n; k++) {
						tmp[i][j]+=a[i][k]*a[k][j];
					}
				}
			}
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
					a[i][j]=tmp[i][j];
				}
			}
		}
		for(int i=0;i<n;i++){
		    for(int j=0;j<n;j++){
		        cout<<b[i][j]<<" ";
		    }
		    cout<<endl;
		}
	}
}

这里使用快速幂的逻辑就是每个部分的计算都是乘法，那么同理的可以用快速幂的方式优化乘法的计算，然后对于算子，是矩阵，所以要实现矩阵的乘法，我这里不方便写在外面，直接内部实现了