백준 문제 11444번 피보나치 수 6 문제풀이 c++

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

11444번: 피보나치 수 6

문제해석

이 문제는 행렬을 이용해서 피보나치 수를 빠르게 구할수 있는 방법을 사용해야한다

피보나치 수열은 첫 두항을 제외하면 다음과 같은데

이 식을 행렬로 나타내면

 

이렇게 쓰면 Fn+2=Fn+1 + Fn 식은 만족하고 초록색 행렬의 아래 부분은 모순이 없게 적당히 채워주면 된다.

그렇게 완성한 행렬은 다음과 같다.

이 식으로 부터 

빨간 부분의 식을 얻을 수있고 F0은 0이므로

1 1

1 0 의 n-1제곱의 1행 1열이 Fn값이 된다.

이걸 바탕으로 코드를 작성했다.

 

코드

#include <iostream>
#include <stack>
typedef long long int ll;
using namespace std;
void ans_ans();
void ans_base();
stack <bool> st;
ll base[2][2]={1,1,1,0};
ll ans[2][2]={1,1,1,0};
ll tmp[2][2];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    ll n;
    cin>>n;
    if(n==1)
    {
        cout<<1;
    }
    else
    {
        n=n-1;
        while(n!=0)
        {
            st.push(n&1);
            n=n>>1;
        }
        st.pop();
        while(!st.empty())
        {
            if(st.top()==1)
            {
                ans_ans();
                ans_base();
                //ans=ans*ans*base
            }
            else
            {

                ans_ans();
                //ans=ans*ans
            }
            st.pop();
        }
        cout<<ans[0][0];
    }
}
void ans_base(){
    //ans=ans*ans*base
    for(int i=0; i<2; i++)
    {
        for(int j=0; j<2; j++)
        {
            for(int k=0; k<2; k++)
            {
                tmp[i][j]=((tmp[i][j]%1000000007)+(ans[i][k]%1000000007)*(base[k][j]%1000000007))%1000000007;
            }
        }
    }
    for(int i=0; i<2; i++)
    {
        for(int j=0; j<2; j++)
        {
            ans[i][j]=tmp[i][j];
            tmp[i][j]=0;
        }
    }
}
void ans_ans(){
    //ans=ans*ans
    for(int i=0; i<2; i++)
    {
        for(int j=0; j<2; j++)
        {
            for(int k=0; k<2; k++)
            {
                tmp[i][j]=((tmp[i][j]%1000000007)+(ans[i][k]%1000000007)*(ans[k][j]%1000000007))%1000000007;
            }
        }
    }
    for(int i=0; i<2; i++)
    {
        for(int j=0; j<2; j++)
        {
            ans[i][j]=tmp[i][j];
            tmp[i][j]=0;
        }
    }
}