[백준]11444 - 피보나치 수 6

고려사항

• 피보나치 수니까 재귀나 dp로 풀면 되나 싶었는데, 전에 그런 식으로 푸는 문제가 있었으니까 그거랑은 다르게 풀어야겠지?
• 입력으로 저렇게 큰 수 들어오는거 처음 봤음
• solved.ac 클래스4 문제를 풀고 있는데 divide & conquer 문제가 많아서 이것도 그거겠지 싶었음.

• 이걸 어떻게 분할정복으로 풀지 찾아보니까 피보나치 수의 성질을 갖는 행렬이 있었음.

  \[\begin{bmatrix} F(n+1) & F(n) \\ F(n) & F(n-1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n\]
• 거듭제곱의 형태. 우리가 구하려는 것은 result행렬의 F(n)자리이고, 이는 [0][1]인덱스 접근으로 구할 수 있음. 직전 풀었던 문제인 행렬 제곱의 아이디어를 가져와서, 분할 정복으로 거듭제곱 풀기

코드

#G2_11444_피보나치 수 6

def mul(A,B,MOD):
  res=[[0]*2 for _ in range(2)]
  for i in range(2):
    for j in range(2):
      res[i][j]=(A[i][0]*B[0][j] + A[i][1]*B[1][j])%MOD
  return res
  
def dc(n,mtr,MOD):
  if n==1:
    return mtr
  tmp=dc(n//2,mtr,MOD)
  tmp=mul(tmp,tmp,MOD)
  if n%2:
    tmp=mul(tmp,mtr,MOD)
  return tmp

n=int(input())
base=[[1,1],[1,0]]
MOD=1000000007
print(dc(n,base,MOD)[0][1])