행렬 제곱

• 거듭제곱의 빠른 계산 (Exponentiation by squaring) 을 행렬에 적용하는 문제.
• n*n 행렬의 곱셈은 O(n^3)이고, 빠른 계산 알고리즘을 이용하면 행렬 곱셈을 O(logb)번만 하면 되므로 총 시간 복잡도는 O(n^3logb)
• 정수의 n제곱을 계산하는 곱셈 문제는 그냥 python의 내장 pow 함수로 가능했지만, 행렬은 알고리즘을 직접 구현해야 한다. 사실 행렬 거듭제곱의 빠른 계산은 동차 선형 점화식의 계산에 필요하기 때문에 teflib.combinatorics.linear_homogeneous_recurrence의 일부로 이미 구현되어있다. 여기에서 행렬 거듭제곱 부분만 복사해서 제출했다.

"""Solution code for "BOJ 10830. 행렬 제곱".

- Problem link: https://www.acmicpc.net/problem/10830
- Solution link: http://www.teferi.net/ps/problems/boj/10830

Tags: [BinaryExponentiation]
"""

MOD = 1000


class SqMat(object):
    """A very simple implementation for n x n matrix."""

    def __init__(self, mat):
        self._mat = mat

    def __getitem__(self, row):
        return self._mat[row]

    def __matmul__(self, other):
        ret = []
        for a_row in self._mat:
            ret.append([sum(a * b for a, b in zip(a_row, b_col)) 
                        for b_col in zip(*other._mat)])
        return SqMat(ret)

    def __mod__(self, mod):
        return SqMat([[item % mod for item in row] for row in self._mat])

    def __pow__(self, n, mod=0):
        res = SqMat([[0] * len(self._mat) for _ in self._mat])
        for i, row in enumerate(res):
            row[i] = 1
        m = SqMat([row[:] for row in self._mat])
        while n:
            if n % 2 == 1:
                res @= m
            m @= m
            if mod > 0:
                m %= mod
            n //= 2
        return res % mod if mod > 0 else res
    
    
def main():
    N, B = [int(x) for x in input().split()]
    mat = [[int(x) for x in input().split()] for _ in range(N)]
    
    answer = pow(SqMat(mat), B, MOD)
    
    for row in answer:
        print(*row)


if __name__ == '__main__':
    main()