백준 문제 2086번 피보나치 수의 합 문제풀이 c++

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

2086번: 피보나치 수의 합

 

문제해석

피보나치 F0부터 Fn까지의 합을 Sn이라고 새롭게 정의하면 위 그림과 같다.

즉 Sn=Fn+2 - 1 이므로 Fa부터 Fb까지의 합을 이 식을 통해 구하는것이 가능하다.

Sb-Sa-1이 Fa부터 Fb까지 합이 되므로 우리가 얻어야하는 것은 Fb+2와 Fa+1이 된다.

저번 게시글 https://anwltjdzheldsbql.tistory.com/15 에 사용했던 분할정복을 통한 수열의 거듭제곱 코드를

그대로 가져와서 조금만 바꾸어서 풀었다.

코드

#include <iostream>
#include <stack>
#include <vector>
typedef long long int ll;
using namespace std;
void reset();
void ans_ans();
void ans_base();
vector <ll> v;
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);
    for(int i=0; i<2; i++)
    {
        ll n;
        cin>>n;
        if(i==0)
        {
            n=n+1;
        }
        else
        {
            n=n+2;
        }
        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();
        }
        v.push_back(ans[0][0]);
        reset();
    }
    if(v[1]-v[0]<0)
    {
        cout<<1000000000+v[1]-v[0];
    }
    else
    {
        cout<<v[1]-v[0];
    }
}
void reset(){
    ans[0][0]=base[0][0];
    ans[0][1]=base[0][1];
    ans[1][0]=base[1][0];
    ans[1][1]=base[1][1];
}
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]%1000000000)+(ans[i][k]%1000000000)*(base[k][j]%1000000000))%1000000000;
            }
        }
    }
    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]%1000000000)+(ans[i][k]%1000000000)*(ans[k][j]%1000000000))%1000000000;
            }
        }
    }
    for(int i=0; i<2; i++)
    {
        for(int j=0; j<2; j++)
        {
            ans[i][j]=tmp[i][j];
            tmp[i][j]=0;
        }
    }
}