prologue
因为格式问题被卡了一小时的人是谁我不说。
analysis
首先这个题目如果我们暴力计算的话，时间复杂度是不允许的（矩阵乘法前面有巨大的常数）。
那么我们就考虑怎么用一些巧妙地方法去计算。我们就可以采取两次分治地思想，递归求解。
以下结论显然成立，读者自证不难：
\[A^1 + A^2 + \cdots + A^k = A^1 + \cdots + A^{mid} + A^{mid} * (A^1 + \cdots + A^{mid})
\]
这个就是我们能够递归求解的本质。我们就可以将原来的 \(A_k\) 转换成一个可以递归求解的式子，具体如下：
- 若 \(k = 1\)，则直接返回当前矩阵。
- 若 \(k \neq 1\)，则可以继续递归计算，得出一小段和的值，然后再进行快速幂运算算出来\(\sum_{i=1}^{(k >> 1) << 1}A^i\)，这里并不是直接到 \(k\) 是因为我们对于奇数来说要进行特殊判断。（这里的位运算写的很抽象我知道 /fad）
- 若 \(k\) 为奇数，则我们应当再加上一个 \(A ^ k\)。
接下来就是我们的代码实现了，但是还有一个要注意的：
每一行的最后没有空格！！！，每一个测试数据之后都要输出换行！！！！
code time
**#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rl register ll
#define foa(i, a, b) for(rl i=a; i < b; ++ i)
#define fos(i, a, b) for(rl i=a; i <= b; ++ i)
#define fop(i, a, b) for(rl i=a; i >= b; -- i)
#define ws putchar(' ')
#define wl putchar('\n')
template <class T> inline void waw(T x)
{
if(x > 9) waw(x / 10);
putchar(x % 10 ^ 48);
}
template <class T> inline void ww(T x)
{
if(x < 0) x = ~x + 1, putchar('-');
waw(x);
}
template <class T> inline void read(T &res)
{
char ch = getchar(); bool f = 0; res = 0;
for(; !isdigit(ch); ch = getchar()) f |= ch == '-';
for(; isdigit(ch); ch = getchar()) res = (res << 1) + (res << 3) + (ch ^ 48);
res = f ? ~res + 1 : res;
}
const ll N = 45;
ll n, m;
struct Matrix
{
ll a[N][N];
Matrix () { memset(a, 0, sizeof a); }
inline void init() {memset(a, 0, sizeof a); }
Matrix operator +(const Matrix &x) const
{
Matrix res;
foa(i, 0, n) foa(j, 0, n)
res.a[i][j] = (a[i][j] + x.a[i][j]) % 10;
return res;
}
Matrix operator *(const Matrix &x) const
{
Matrix res;
foa(i, 0, n) foa(k, 0, n) foa(j, 0, n)
res.a[i][j] = (res.a[i][j] + (a[i][k] * x.a[k][j]) % 10) % 10;
return res;
}
} a;
inline Matrix qmi(Matrix t, ll k)
{
Matrix res = t; -- k;
while(k)
{
if(k & 1) res = res * t;
t = t * t;
k >>= 1;
}
return res;
}
inline Matrix calc(Matrix t,ll k)
{
if(k == 1) {return t; } // border cases
Matrix ans, tmp = calc(t, k >> 1);
ans = tmp + (tmp * qmi(t, k >> 1));
if(k & 1) ans = ans + qmi(t, k);
return ans;
}
int main()
{
while(scanf("%lld%lld", &n, &m) && n)
{
a.init();
foa(i, 0, n) foa(j, 0, n) read(a.a[i][j]), a.a[i][j] %= 10;
Matrix ans = calc(a, m);
foa(i, 0, n)
{
foa(j, 0, n)
{
waw(ans.a[i][j]);
if(j != n - 1) ws;
}
wl;
}
wl;
}
return 0;
}