def multiply(A,B):
S = [[0]*M for i in range(M)]
for i in range(M):
for j in range(M):
for k in range(M):
S[i][j] += A[i][k]*B[k][j]
S[i][j] %= 10**9+7
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())
print(cal([[int(i==j==0 or i==M-1 and j==0 or j-i==1) for j in range(M)] for i in range(M)],N)[0][0])
간단한 인접행렬 경우의 수 문제
길의 개수 [백준 1533번] 길의 개수 (Python3) (tistory.com) 하위호환격 문제이다.
길의 개수 문제를 풀었을 때, x에서 y까지 걸리는 시간이 n초인 경우 행을 n개로 쪼갰던 것처럼, 이 문제는 1에서 1까지 가는 경로가 M초가 걸리는 길이 있다고 생각하고, 행을 M개로 쪼갠 뒤 M초 후에 1에 도착하도록 행렬을 짜면 된다.
그리고 위에서 짠 행렬을 분할정복을 통한 거듭제곱으로 N번 제곱해주면 된다.
오늘의 교훈) 인접행렬은 유용하다.