矩阵快速幂

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;

typedef long long lld;
const int M = 1e9 + 7, N = 105;
lld n, k;
struct Mx{
	lld m[N][N];
}a, ori;

Mx mxmul(Mx u, Mx v, int h, int l, int q, int p)
{
	Mx tmp = ori;
	for(int i = 1; i <= h; i++) {
		for(int k = 1; k <= q; k++) {
			for(int j = 1; j <= l; j++) {
				tmp.m[i][j] = (u.m[i][k] * v.m[k][j] + tmp.m[i][j]) % p;
			}
		}
	}
	return tmp;
}

Mx mxpow(Mx tmp, lld q, int p)
{
	Mx mx = ori;
	for(int i = 1; i <= n; i++)
		mx.m[i][i] = 1;
	while(q) {
		if(q % 2) {
			mx = mxmul(mx, tmp, n, n, n, p);
		}
		tmp = mxmul(tmp, tmp, n, n, n, p);
		q /= 2;
	}
	return mx;
}
int main()
{
	scanf("%lld%lld", &n, &k);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			scanf("%lld", &a.m[i][j]);
		}
	}
	a = mxpow(a, k, M);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			printf("%lld ", a.m[i][j]);
		}
		printf("
");
	}
return 0;
}