제곱시키는 문제 B의 범위가 매우크다 1 ≤ B ≤ 100,000,000,000
내코드의 작동방식은 다음과 같다
행렬의 곱셈을 B번만큼 하는것이다 다만 보면 B가 무려 천억이라는 말도안되는 숫자를 가지고있어서
코드를 짜면서도 분명히 시간초과가 될것이라고 예상했고 그것은 사실이었다
제출해보니 역시 예상대로 0%도 넘기지 못하고 시간초과되었다
만약 B번만큼 연산을 반복하는게 아니라면 어떤 규칙이 있는것일까
직접 확인해보도록 한다
잠깐 혹시 이게 통하는지 궁금해졌다
그러니까
행렬
1 2
3 4
의 제곱끼리 곱했을때
행렬
1 2
3 4
의 4제곱이 나오는지 말이다
만약 이게 된다면
시간을 절약 할수있을것이다
된다
그렇다면 행렬 제곱이었던것을 쪼갤수있을것이다
그렇게 해서 제출했는데시간초과가떳다
아차차
저장기능을 활용해서 다시 제출하니 이번엔 맞았다
# 행렬 제곱
d={}
def mod(a,b):
return (a*b)%1000
def multiply(array_A,array_B): # 행렬곱을 하는 함수: 두 행렬을 입력값으로 받아 결과를 제출
big_array=[]
for i in range(N):
array=[]
for j in range(N):
sumed=0
for k in range(N):
sumed+=mod(array_A[i][k],array_B[k][j])
array.append(sumed%1000)
big_array.append(array)
return big_array
def divide(matrix,B):
# print(B)
try:
return d[B]
except:
if B==1:
d[B]=matrix
return d[B]
else:
dd=B//2
d[B]=multiply(divide(matrix,dd),divide(matrix,B-dd))
return d[B]
N,B=map(int,input().split())
array_A=[]
for i in range(N):
array_A.append([i%1000 for i in list(map(int,input().split()))])
# sumed=array_A
# for i in range(1,B):
# sumed=multiply(sumed,array_A)
result=divide(array_A, B)
for i in result:
print(*i)
히스토그램에서 가장 큰 직사각형 (0) | 2023.01.08 |
---|---|
피보나치수 6 파이썬 (0) | 2022.12.24 |
이항계수3 파이썬 (0) | 2022.12.11 |
알고리즘 수업 - 병합 정렬 1 파이썬 풀이 (0) | 2022.10.28 |
주가 예측 5 (0) | 2022.10.14 |