luogu3390 【模板】矩阵快速幂

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
ll k;
const ll mod=1e9+7;
struct Matrix{
	int n;
	ll num[105][105];
	Matrix operator *(const Matrix &b)const{
		Matrix res=b;
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++){
				res.num[i][j] = 0;
				for(int k=1; k<=n; k++)
					res.num[i][j] = (res.num[i][j]+num[i][k]*b.num[k][j]%mod)%mod;
			}
		return res;
	}
	Matrix operator ^(ll k)const{
		Matrix res;
		Matrix x = *this;
		res.n = n;
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				if(i==j)	res.num[i][j] = 1;
				else		res.num[i][j] = 0;//搞成一个单位矩阵，单位矩阵乘矩阵A等于矩阵A本身。
		while(k){
			if(k&1)	res = res * x;
			x = x * x;
			k >>= 1;
		}
		return res;
	}
}a;
int main(){
	cin>>a.n>>k;
	for(int i=1; i<=a.n; i++)
		for(int j=1; j<=a.n; j++)
			scanf("%lld", &a.num[i][j]);
	a = a ^ k;
	for(int i=1; i<=a.n; i++){
		for(int j=1; j<=a.n; j++)
			printf("%lld ", a.num[i][j]);
		printf("
");
	}
	return 0;
}