## 【UVA-11149】Power of Matrix【矩阵快速幂】

【UVA-11149】Power of Matrix【矩阵快速幂】

Solution：

$$A + A^2 + A^3 + … + A^k = (A + A^2 + … + A^{k / 2})(E + A^{k / 2})$$

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int MOD = 10;
const int LIM = 40 + 10;
struct Matrix {
int v[LIM][LIM];
int size;
Matrix operator * (const Matrix & m) const {
Matrix ret = {{0}};
ret.size = size;
for (int i = 0; i < size; i++) {
for (int k = 0; k < size; k++) {
if (v[i][k])
for (int j = 0; j < size; j++) {
ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]) % MOD;
}
}
}
return ret;
}
Matrix operator + (const Matrix & m) const {
Matrix ret = {{0}};
ret.size = size;
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++)
ret.v[i][j] = (v[i][j] + m.v[i][j]) % MOD;
return ret;
}
};
int n;
Matrix iden, base;

inline void init() {
memset(&iden, 0, sizeof iden);
for (int i = 0; i < n; i++) iden.v[i][i] = 1;
iden.size = n;
memset(&base, 0, sizeof base);
base.size = n;
}

Matrix fastPow(int p, Matrix m) {
Matrix ret = {{0}};
ret.size = m.size;
for(int i = 0; i < ret.size; i++) ret.v[i][i] = 1;
while (p) {
if (p & 1) ret = ret * m;
if (p) m = m * m;
p >>= 1;
}
return ret;
}

Matrix binarySum(int k) {
if (k == 1) return base;
else if (k & 1) return binarySum(k >> 1) * (iden + fastPow(k >> 1, base)) + fastPow(k, base);
else return binarySum(k >> 1) * (iden + fastPow(k >> 1, base));
}

int main() {
int k;
while (~scanf("%d", &n) && n) {
scanf("%d", &k);
init();
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
scanf("%d", &base.v[i][j]);
base.v[i][j] %= MOD;
}
Matrix ans = binarySum(k);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (j) putchar(' ');
printf("%d", ans.v[i][j]);
}
putchar('\n');
}
putchar('\n');
}
return 0;
}