题解 UVA11149 【Power of Matrix】
皎月半洒花
2019-03-09 11:02:47
其实是一个构造题。
我们思考朴素的$Matrix-pow$是$O(n^3\log m)$的，放在这道题里面并不适用，因为我们暴力$Matrix-pow$是$O(mn^3 \log m)$，即使线性递推也是$O(mn^3)$的。
计$A^u$为当前矩阵的$u$次幂，那么我们不妨构造一个复合矩阵
$$\begin{bmatrix} A^k\\ S_k \end{bmatrix}$$
其中
$$S_i = \sum \limits_{j = 1}^{i}A^i$$
我们发现它可以这么转移：
$$\begin{bmatrix} A^k\\ S_k \end{bmatrix} = \begin{bmatrix}A^{k-1}\\S_{k-1}\end{bmatrix}\cdot \begin{bmatrix}A &0\\I_n&I_n\end{bmatrix}$$
其中$I_n$表示$n$阶单位矩阵。
那么这就很好做了…
但是有可能会被卡输出/输入格式…这是个玄学问题……我把输入改成`while (cin >> N >> K && N)`才$A$掉……
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#define Mod 10
#define LL long long
using namespace std ;
int N, K, i, j ;
struct Matrix{
LL M[240][240] ;
void clear() { memset(M, 0, sizeof(M)) ;}
void reset() {
clear() ;
for (int i = 1 ; i <= N ; ++ i) M[i][i] = 1 ;
}
Matrix friend operator *(const Matrix&A, const Matrix &B){
Matrix Ans ; Ans.clear() ;
for (int i = 1 ; i <= N; ++ i)
for (int j = 1 ; j <= N ; ++ j)
for (int k = 1 ; k <= N; ++ k)
Ans.M[i][j] = (Ans.M[i][j] + A.M[i][k] * B.M[k][j]) % Mod ;
return Ans ;
}
Matrix friend operator +(const Matrix&A, const Matrix &B){
Matrix Ans ; Ans.clear() ;
for (int i = 1 ; i <= N; ++ i)
for (int j = 1 ; j <= N ; ++ j)
Ans.M[i][j] = (A.M[i][j] + B.M[i][j]) % Mod ;
return Ans ;
}
} base, ans ;
inline Matrix expow(Matrix T, LL P){
Matrix Ans ; Ans.reset() ;
while (P){
if (P & 1) Ans = Ans * T ;
T = T * T, P >>= 1 ;
}
return Ans ;
}
int main(){
while (cin >> N >> K && N){
base.clear(), ans.clear() ;
for (i = 1 ; i <= N ; ++ i){
for (j = 1 ; j <= N ; ++ j)
scanf("%d", &base.M[i][j]) ;
base.M[N + i][i] = base.M[N + i][N + i] = 1 ;
}
N <<= 1 ;
ans = expow(base, K + 1) ;/*
for (i = 1 ; i <= N ; ++ i, putchar('\n'))
for (j = 1 ; j <= N ; ++ j)
printf("%d ", ans.M[i][j]) ;*/
N >>= 1 ;
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j <= N ; ++ j){
LL Out = ans.M[N + i][j] % Mod ;
if (i == j) Out = (Out + Mod - 1) % Mod ;
printf("%lld", Out) ; if (j == N) cout << endl ; else cout << " " ;
}
cout << endl ;
}
}
```