矩阵乘法

别人的博客

Luogu - P3390 【模板】矩阵快速幂

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout<<#x<<" = "<<x<<endl;
const int N = 105, M = 1e9 + 7;
int n;
ll k;
inline ll read() {
	ll s = 0, f = 1; char c = getchar();
	while (c < '0' || c>'9') { if (c == '-')f = -1; c = getchar(); }
	while (c >= '0' && c <= '9') { s = (s << 1) + (s << 3) + (c ^ 48); c = getchar(); }
	return s * f;
}
struct Matrix {
	ll val[N][N];

	void init() { memset(val, 0, sizeof val); }
	void build() { for (int i = 1; i <= n; i++)val[i][i] = 1; }  //构造单位矩阵

	Matrix operator *(Matrix tmp) {  //重载运算符，当看到 Matrix 类型的 * 号时，会自动识别并运算
		Matrix ans;
		ans.init();  //一定要清空
		for (int k = 1; k <= n; k++)
			for (int i = 1; i <= n; i++)
				for (int j = 1; j <= n; j++)
					ans.val[i][j] = (ans.val[i][j] + val[i][k] * tmp.val[k][j] % M) % M;
		return ans;
	}
}A, Ans;
int main() {
	n = read(), k = read();
	Ans.build();
	for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)A.val[i][j] = read();
	while (k) {	 //矩阵快速幂
		if (k & 1)Ans = Ans * A;
		A = A * A;
		k >>= 1;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)cout << Ans.val[i][j] << ' ';
		cout << endl;
	}
	return 0;
}