题解 UVA11149 【Power of Matrix】

· · 题解

其实是一个构造题。

我们思考朴素的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掉……

#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 ;
    }
}