피보나치 수의 합

문제 분석 및 풀이

설계 분석

• 피보나치의 여러 성질, 빠르게 피보나치를 빠르게 구하는 방법을 알아야 풀 수 있는 문제

• 피보나치 수열의 합에 관한 성질을 알야야 함.

  • 

  • 피보나치에 관한 여러 성질들

• 피보나치 수열을 행렬의 거듭제곱을 통해서 구하는 방법을 알아야함

  • $O(logN)$으로 가능
  • 피보나치를 구하는 방법들

풀이

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1000000;

vector<vector<long long>> base =
{
    {1,1},
    {1,0}
};

vector<vector<long long>> current;

vector<vector<long long>> matrix_time(vector<vector<long long>> A, vector<vector<long long>> B)
{
    vector<vector<long long>> res = vector<vector<long long>>(A.size(), vector<long long>(B[0].size()));
    for (int i=0; i<2; i++)
    {
        for (int j=0; j<2; j++)
        {
            long long sum = 0;
            for (int k=0; k<2; k++)
            {
                sum += A[i][k] * B[k][j];
            }
            res[i][j] = sum % MOD;
        }
    }

    return res;
}

vector<vector<long long>> matrix_power(vector<vector<long long>> arr, long long i)
{
    vector<vector<long long>> res = {{1,0},{0,1}};
    while (i > 0)
    {
        if (i % 2 == 1)
        {
            res = matrix_time(res, arr);
        }
            arr = matrix_time(arr, arr);
        i /= 2;
    }

    return res;
}

long long fibo(long long i)
{
    vector<vector<long long>> A =
    {
        {1,1},
        {1,0}
    };

    A = matrix_power(A, i);

    return A[1][0];
}


long long Sol(long long left, long long right)
{
    long long l_1 = fibo(left+1) % MOD;
    long long r_2 = fibo(right+2) % MOD;

    long long sum = ((r_2 - l_1) + MOD) % MOD;

    return sum;
}

int main()
{
    long long l, r;

    cin >> l >> r;

    long long res = Sol(l, r);

    cout << res << "\n";

    return 0;
}