★Divide & Conquer Expert(Easy) I - 1 Solved★

★ 11440 피보나치 수의 제곱의 합 ★

n=int(input())
BIG=1_000_000_007

def get_power(a,b,c):
    if b <= 1:
        return [[a[0][0]%BIG,a[0][1]%BIG],[a[1][0]%BIG,a[1][1]%BIG]]
        
    x = get_power(a,b//2,c)

    if b % 2 == 0:
        return prod(x,x)
    else:
        return prod(prod(x,x),a)

def prod(A,B):
    a,b,c,d=A[0][0],A[0][1],A[1][0],A[1][1]
    e,f,g,h=B[0][0],B[0][1],B[1][0],B[1][1]
    return [[(a*e+b*g)%BIG,(a*f+b*h)%BIG],[(c*e+d*g)%BIG,(c*f+d*h)%BIG]]

core = [[1,1],[1,0]]

matrix_1 = get_power(core,n-1,BIG)
matrix_2 = get_power(core,n,BIG)
print(((matrix_1[0][0]%BIG)*(matrix_2[0][0]%BIG))%BIG)

 

🙉 F1부터 Fn까지의 모든 피보나치 수의 제곱의 합은 아래와 같이 Fn*Fn+1 결과로 표현할 수 있다.

🙉 이 때 Fn에서의 n이 매우 큰 수이므로 Fn을 구하기 위해 분할정복을 이용한 행렬 거듭제곱으로 O(logn)만에 구해야 한다. Fn과 Fn+1을 각각 O(logn)만에 구한 뒤, modulo multiplication property에 의해 ((Fn%BIG) * (Fn+1%BIG))%BIG를 최종 답으로 출력!

---