글 읽기 - 행렬의곱 왜 틀린걸까요?

wowjd123589 2년 전 0

질문)이진수로 안바꾸고 //2를 반복하는 방식으로 (결국 2이진수한것같은 효과 생김) 풀었는데요

비슷한 문제로 1629번, 13171번 처럼

고속거듭제곱방법이랑 //2이용 써서 풀려고 하는데 잘안됩니다.

어디가 틀린걸까요?

#행렬 곱셈 함수
def matrix_mul(a, b):
    result = [[0]* N for _ in range(N)]#초기화
    
    #행렬곱
    for i in range(N):
        for j in range(N):
            for k in range(N):
                result[i][j] += a[i][k] * b[k][j]
    
    #행렬곱결과의 각 원소 %1000
    for i in range(N):
        for j in range(N):
            result[i][j] %= 1000
                
    return result




def power(a,b):
 #단위 행렬
 identity_matrix = [[1 if i == j else 0 for i in range(N)] for j in range(N)]
 global C

 if b==0:
    return identity_matrix #1

#x=power(a,b//2)%C
 x=power(a,b//2)
 for i in range(N):
   for j in range(N):
      x[i][j]%=C

 if b%2==0:
   return matrix_mul(x, x)#x*x
 else:
   return matrix_mul(a, matrix_mul(x, x))#x*x*a

N,b=map(int,input().split())

#n*n행렬을 이차원배열로 입력받는 방법
arr=[[0 for i in range(N)] for i in range(N)] #A
for i in range(N):
    arr[i]=list(map(int,input().split()))

C=1000
#ans=power(arr, b)%C
ans=power(arr,b//2)
for i in range(N):
        for j in range(N):
            ans[i][j]%=C
for row in range(N):
    print(ans[row])

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

행렬의곱 왜 틀린걸까요?

wowjd123589 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말