数论：矩阵加速、矩阵快速幂

点击查看代码块

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mode=1e9+7;
int n;
ll k;
struct Matrix{
	ll a[110][110];//一定要用long long存 
	Matrix(){memset(a,0,sizeof(a));}
	Matrix operator * (const Matrix & b) const {
		Matrix ret;
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
				for (int k=1;k<=n;k++){
					ret.a[i][j]=(ret.a[i][j]+a[i][k]*b.a[k][j]) % mode;
				}
		return ret;
	}
}base,ans;

void init(int n){
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			scanf("%d",&base.a[i][j]);
			ans.a[i][j]=base.a[i][j];
		}
	}
}

void q_pow(ll b){
	while(b){
		if(b&1) ans=base*ans;
		base=base*base;
		b>>=1;
	}
}


int main(){
	scanf("%d %lld",&n,&k);
	init(n);
	if(k==1 || k==0){
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++){
				printf("%d ",ans.a[i][j]);
			}
			printf("
");
		}	
	}
	else{
		q_pow(k-1);
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++){
				printf("%d ",ans.a[i][j]);
			}
			printf("
");
		}	
	}
	return 0;
}