_pks 'w blog

_pks 'w blog

除了勇气,我什么都不缺。

题解 UVA11149 【Power of Matrix】

posted on 2019-03-09 11:02:47 | under 题解 |

其实是一个构造题。

我们思考朴素的 $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 ;
    }
}