mod = 10**9+7
def multiply(A,B):
S = [[0]*len(B[0]) for i in range(len(A))]
for i in range(len(A)):
for j in range(len(B[0])):
for k in range(len(B)):
S[i][j] += A[i][k]*B[k][j]
S[i][j] %= mod
return S
def cal(A,n):
if n==0:
return [[int(i==j) for j in range(M)] for i in range(M)]
if n==1:
return A
c = cal(A,n//2); c2 = multiply(c,c)
return multiply(c2,A) if n%2 else c2
N,M = map(int,input().split()); N-=1
matrix = cal([[int(abs(i-j)<3)+int(j==i and 0!=j!=M-1) for j in range(M)] for i in range(M)],N//2)
print(0 if M==1 and N else sum(map(sum,multiply(matrix,[[1+int(N%2 and 0!=i!=M-1)] for i in range(M)])))%mod)인접행렬 경로 문제
일하는 세포 [백준 17401번] 일하는 세포 (Python3) (tistory.com) 나 길의 개수 [백준 1533번] 길의 개수 (Python3) (tistory.com) 와 비슷한 방식으로 해결할 수 있다.
풀이를 설명하면,
1. 홀수번째 행과 짝수번째 행을 하나의 묶음으로 생각한다.
2. 1에서 묶었을 때 각 칸에 대해서 경로에 대한 행렬을 생성한다. 즉, 현재 칸에서 2행 밑으로 내려갈 때 갈 수 있는 칸 +1을 해주면 된다.
3. 분할정복을 통한 거듭제곱으로 경로의 개수를 세어준다.
4. 만약 N-1이 홀수인 경우 (N-1인 이유는 마지막 행에서는 이동하지 않으므로) 마지막 행이 두개로 묶을 수 없기 때문에 따로 취급해서 한번 더 경로에 대한 행렬곱셈을 해주어야한다.
5. M이 1인 경우 0을 출력해야 한다. 이때 N도 1인 경우에는 1을 출력해야한다.
5번의 예외처리 때문에 약간 까다로웠던 문제였다. 풀이 자체는 인접행렬에 익숙하다면 금방 생각해낼 수 있다.
여담) 내 풀이가 숏코딩 순위 1위가 되었다.
