[BOJ 11444, 약간 쉬움] 피보나치 수 6 (C++)

개인적인 난이도

약간 쉬움

 

알면 풀고 모르면 못푼다

모르겠어서 아이디어 부분을 구글링하고 구현만 내가 했다

---

복습)

피보나치 수열을 컴퓨터로 표현하는 방법은 여러 가지가 있다.

1. 재귀함수를 이용해 계산한다

2. dp를 이용해 계산한다

3. (오늘 배울 방법) : 행렬의 거듭제곱을 이용해 계산한다.

 

 

 

 

 

1. 기본적인 모듈러 연산의 성질을 알아야 한다.

모듈러 연산의 합/차/곱에 대해 교환법칙과 분배법칙이 성립함을 알고 있으면 된다. 입력과 출력 사이의 과정에서 매우 큰 수를 다뤄야 할 때 자주 나온다.

 

2. 분할정복을 이용한 거듭제곱을 할 줄 알아야 한다

https://www.acmicpc.net/problem/1629

1629번: 곱셈

반복되는 연산을 log N 속도로 계산할 수 있다. 코드의 형태가 머리에 잘 안들어가므로 그냥 풀이를 외웠다

 

3. 피보나치 수를 행렬로 표현할 수 있음을 알아야 한다.

https://youtu.be/uX2IsIykLJc

대학교 선형대수학 수업을 한 귀로 듣고 한 귀로 내보냈더니 이걸 몰랐음

피보나치 수열의 n번째 항을 행렬의 거듭제곱 형태로 나타낼 수 있고, 대각화를 통해 일반항까지 구할 수 있다고 한다

위의 동영상을 참고하는 게 이해가 가장 빠르겠다.

 

그냥 피보나치 수열을 행렬로 나타낼 수 있겠다 ->>> 라는 아이디어로 출발을 한다

An+1

An

이런 2*1짜리 행렬을 생각해보면

이렇게 1*2 행렬과 2*1 행렬의 곱으로 피보나치 수열의 형태를 만들 수 있다

그리고 아래에다가 [1 0] 을 붙이면 깔끔하게 피보나치가 나옴

 

성공한 코드

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
using namespace std;

const int divnum = 1e9+7;

void mulmat(vector<ll> a,vector<ll> b,vector<ll> &c){
    c[0]=(a[0]*b[0])%divnum+(a[1]*b[2])%divnum;
    c[1]=(a[0]*b[1])%divnum+(a[1]*b[3])%divnum;
    c[2]=(a[2]*b[0])%divnum+(a[3]*b[2])%divnum;
    c[3]=(a[2]*b[1])%divnum+(a[3]*b[3])%divnum;
    c[0]%=divnum;
    c[1]%=divnum;
    c[2]%=divnum;
    c[3]%=divnum;
}

int main(void) {
    fastio;
    uint64_t n;cin>>n;
    vector<ll> v={1,1,1,0};
    vector<ll> ans={1,1,1,0};
    n--;

    while (n)
    {
        if(n%2==1){
            mulmat(ans,v,ans);
        }
        n=n>>1;
        mulmat(v,v,v);
    }
    cout<<ans[1]%divnum;
    return 0;
}