洛谷P3390 【模板】矩阵快速幂 题解 矩阵快速幂模板题

题目链接：https://www.luogu.com.cn/problem/P3390

矩阵快速幂模板题。

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
const long long mod = 1e9 + 7;struct Matrix {int n, m;long long a[maxn][maxn];void init(int _n, int _m) {n = _n;m = _m;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)a[i][j] = 0;}Matrix operator * (const Matrix &b) const {Matrix res;res.init(n, b.m);for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)for (int k = 1; k <= b.m; k++)res.a[i][k] += a[i][j] * b.a[j][k],res.a[i][k] %= mod;return res;}Matrix operator ^ (long long k) const {Matrix res, t;res.init(n, n);for (int i = 1; i <= n; i++)res.a[i][i] = 1;t.init(n, n);memcpy(t.a, a, sizeof a);for (; k; k >>= 1, t = t * t)if (k & 1ll)res = res * t;return res;}
} a;
int n;
long long k;int main() {cin >> n >> k;a.init(n, n);for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)cin >> a.a[i][j];a = a ^ k;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++)cout << a.a[i][j] << " ";cout << endl;}return 0;
}