#include <bits/stdc++.h> typedef long long ll; const int maxx = 110; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; #define mod(x) ((x) % mod) using namespace std; int n; struct mat { int m[maxx][maxx]; } unit; //矩阵 mat operator*(mat a, mat b) { //重载矩阵乘法 mat res; ll x; //可能爆int for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { x = 0; for (int k = 0; k < n; k++) x += mod((ll)a.m[i][k] * b.m[k][j]); res.m[i][j] = mod(x); } return res; } void init_unit() { //定义单位矩阵 for (int i = 0; i < maxx; i++) unit.m[i][i] = 1; return; } mat pow_mat(mat a, ll n) { //矩阵快速幂,跟快速幂形式上差不多 mat res = unit; while (n) { if (n & 1) res = res * a; a = a * a; n >>= 1; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll x; init_unit(); while (cin >> n >> x) { mat a; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> a.m[i][j]; a = pow_mat(a, x); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { if (j + 1 == n) cout << a.m[i][j] << endl; else cout << a.m[i][j] << " "; } } return 0; }
#include <algorithm> #include <functional> #include <queue> #include <deque> #include <string> #include <vector> #include <stdio.h> #include <string.h> #include <iostream> typedef long long ll; const int maxx = 110; const int inf = 0x3f3f3f3f; const int mod = 1e4; using namespace std; int n = 2; struct mat { int m[maxx][maxx]; } unit; mat operator*(mat a, mat b) { mat res; ll x; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { x = 0; for (int k = 0; k < n; k++) x = (x + a.m[i][k] * b.m[k][j]) % mod; res.m[i][j] = x % mod; } return res; } void init_unit() { for (int i = 0; i < maxx; i++) unit.m[i][i] = 1; return; } mat pow_mat(mat a, ll n) { mat res = unit; while (n) { if (n & 1) res = res * a; a = a * a; n >>= 1; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll x; init_unit(); while (cin >> x && x != -1) { mat a; a.m[0][0] = 1; a.m[0][1] = 1; a.m[1][0] = 1; a.m[1][1] = 0; a = pow_mat(a, x); cout << a.m[0][1] << endl; } return 0; }