M8 - 矩阵乘法与快速幂

class matrix {
	static matrix& multi(matrix &ret, matrix &a, matrix &b, int n, int x, int m) {
		for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
			ret.ar[i][j] = 0;
			for (int k = 0; k < x; k++) ret.ar[i][j] += a.ar[i][k] * b.ar[k][j];
		}
		return ret;
	}
public:
	int ar[maxn][maxn];
	static matrix& qpow(matrix &ret, matrix &x, int a, int n) {
		static matrix tmp;
		for (int i = 0; i < n; i++) fill(ret.ar[i], ret.ar[i]+n, 0), ret.ar[i][i] = 1;
		while (a) {
			if (a&1u) swap(multi(tmp, ret, x, n, n, n), ret);
			swap(multi(tmp, x, x, n, n, n), x);
			a >>= 1u;
		}
		return ret;
	}
	void output(int n, int m) {
		for (int i = 0; i < n; i++) {
			printf("%d", ar[i][0]);
			for (int j = 1; j < m; j++) printf(" %d", ar[i][j]);
			putchar(10);
		}
	}
} x, ret;

int n, a;
cin >> n >> a;
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> x.ar[i][j];
matrix::qpow(ret, x, a, n).output(n, n);