[백준 16467번] 병아리의 변신은 무죄 (Python3)

mod = 10**8+7

def multiply(A,B):
  S = [[0]*K for i in range(K)]
  for i in range(K):
    for j in range(K):
      for k in range(K):
        S[i][j] += A[i][k]*B[k][j]
      S[i][j] %= mod
  return S

def cal(A,n):
  if n==1:
    return A
  c = cal(A,n//2); c2 = multiply(c,c)
  return multiply(c2,A) if n%2 else c2

for _ in range(int(input())):
  K,N = map(int,input().split()); K += 1
  matrix = [[0]*K for i in range(K)]
  matrix[0][0] += 1; matrix[0][-1] += 1
  for i in range(K-1):
    matrix[i+1][i] = 1
  print(cal(matrix,N)[0][0])

간단한 행렬 거듭제곱 문제

피보나치 수 문제를 푸는것과 비슷한 원리로 풀면 된다.

 

병아리가 알을 낳으면 K일 후에 부화한다. 즉, 오늘 낳은 알은 K+1일 뒤에 부화한다.

이를 통해 "N일의 병아리 수 = N-1일의 병아리 수 + N-1-K일의 병아리 수" 라는 점화식이 성립함을 알 수 있다.

 

점화식을 구했으니, 이제 할일은 피보나치 수열을 풀때처럼 행렬을 구하고 행렬을 N번 거듭제곱 해주는 것 뿐이다.

 

 

참고로 이 문제는 mod가 10^9+7이 아닌 10^8+7이다.... 나뿐만 아니라 많은 사람들이 이거때문에 낚인것 같다.