문제
- 크기가 N*N인 행렬 A가 주어진다.
- 이때, A의 B제곱을 구하는 프로그램을 작성한다.
- 수가 커지지 않기 위해 A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.
입력
첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000)
둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.
아이디어
A^n 이 있다고 생각하자.
\begin{align*}
A^{11} &= (A^{5})^2 \cdot A \\
A^{10} &= (A^{5})^2
\end{align*}
거듭제곱 연산 생각해보기
python
"""
z[1][1] = x[1][1]*y[1][1]
+ x[1][2]*y[2][1]
+ x[1][3]*y[3][1]
z[2][1] = x[2][1]*y[1][1]
+ x[2][2]*y[1][2]
+ x[2][3]*y[1][3]
-------------------------------------------------------------
z[a][b] = x[a][i] * x[i][b]
+ x[a][i] * x[i][b]
+ x[a][i] * x[i][b]
+ x[a][i] * x[i][b]
+ x[a][i] * x[i][b]
---------------------------------------------------------------
"""
for a in range(n):
for b in range(n):
# z[a][b] 값 구하기
for i in range(n):
z[a][b] += (temp[a][i] * temp[i][b]) % 1000
- n =1 이면 그냥 계산한다.
- n = (짝수) 이면 거듭제곱 값 생각해보기
A^{n} = A^{n//2}~\cdot~A^{n//2}
= \text{temp} \cdot \text{temp}
- n = (홀수) 이면 거듭제곱한 값 곱하기
A^{n} = A^{n//2}~\cdot~A^{n//2}\cdot~A
= \text{temp} \cdot \text{temp} \cdot A
python
def power():
if n == 1:
return temp
else:
for a in range(n):
for b in range(n):
# z[a][b] 값 구하기
for i in range(n):
z[a][b] += (temp[a][i] * temp[i][b]) % 1000
for a in range(n):
for b in range(n):
# z[a][b] 값 구하기
for i in range(n):
z[a][b] += (temp[a][i] * A[i][b]) % 1000
코드
python
# 행렬 제곱
import sys
input = sys.stdin.readline
def multiply(A, B):
n = len(A)
C = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
# c[i][j]의 값 구하기
for k in range(n):
C[i][j] += (A[i][k] * B[k][j]) % 1000
return C
def power(A, n):
# 지수가 1인 경우
if n == 1:
return A
# 지수가 짝수인 경우
if n % 2 == 0:
temp = power(A, n//2)
return multiply(temp, temp)
# 지수가 홀수인 경우
else:
temp = power(A, n-1)
return multiply(temp, A)
if __name__ == "__main__":
n, b = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(n)]
ans = power(A, b)
for i in range(n):
for j in range(n):
print(ans[i][j] % 1000, end=" ")
print("")