|
n, b = map(int, input().split())
A = []
for i in range(n) :
A.append(list(map(int, input().split())))
I = [[0 for i in range(n)] for j in range(n)]
for i in range(n) :
I[i][i] = 1
def mult(A, B) :
C = [[0 for i in range(n)] for j in range(n)]
for i in range(n) :
for j in range(n) :
sum = 0
for x in range(n) :
sum = sum + A[i][x] * B[x][j]
C[i][j] = sum % 1000
return C
powerlist = [0 for i in range(37)]
for i in range(n) :
for j in range(n) :
A[i][j] = A[i][j] % 1000
powerlist[0] = A
for i in range(1, 37) :
powerlist[i] = mult(powerlist[i-1], powerlist[i-1])
bilist = [0 for i in range(37)]
for i in range(36, -1, -1) :
bilist[i] = b // pow(2, i)
b = b - bilist[i] * pow(2, i)
ans = [[] for i in range(n)]
if bilist[0] == 1 :
for i in range(n) :
ans[i] = powerlist[0][i][:]
else :
for i in range(n) :
ans[i] = I[i][:]
for i in range(1, 37) :
if bilist[i] == 1 :
ans = mult(ans, powerlist[i])
for i in range(n) :
for j in range(n-1) :
print(ans[i][j] , end = ' ')
print(ans[i][-1])
|
행렬의 곱셈도 정수의 곱셈처럼 결합법칙이 성립한다.
즉, 행렬곱함수나 항등원같이 필요한 것을 만들어준다면 백준 1629번 곱셈과 똑같은 방법으로 풀 수 있다.
행렬을 곱해 mod1000을 남기는 함수 mult를 정의하고, 항등원 I를 만든다.
이후 1629에서 쓴 코드를 자료형에 맞게 갖다 쓰면 끝
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
| 파이썬 백준 10828 스택 (0) | 2021.11.12 |
|---|---|
| 파이썬 백준 2261 가장 가까운 두 점 (0) | 2021.11.12 |
| 파이썬 백준 1629 곱셈 (0) | 2021.11.12 |
| 파이썬 백준 2630 색종이 만들기 (0) | 2021.11.12 |
| 파이썬 백준 8983 사냥꾼 (0) | 2021.11.12 |