2086번

2086번 - 피보나치 수의 합

이 문제는 일단 주어지는 값들의 범위가 너무나 크다. 시간초과가 가장 큰 문제가 됐다.

일단 행렬을 이용하면 N번째 피보나치의 수는 log(N) 의 값에 구할 수 있기 때문에 문제가 되지 않았다.

그래서 처음에는 for문을 통해서 a에서 b까지 피보나치의 수를 모두 구하려고 했다.. 그런데 생각해보니

최악의 경우 a=1 , b=9000000000000000000 이 되면 시간제한 1초를 무조건 넘기게 된다...

구간의 합을 빠르게 구하는 아무리 찾아봐도 O(N)밖에 없었다.. 그래서 다른 분들 코드를 보는데!

피보나치의 수의 합을 빠르게 구하는 식이 있었다.

바로 1에서 N까지의 피보나치 수의 합 = N+2 번째 피보나치 수 - 1 이었다.

이를 이용하면 쉽게 답을 구할 수 있었다.

추가적으로 모듈러를 사용할 때 (A-B)%M에서

A-B 는 음수값이 나올 수 있으므로 (A%M - B%M + M)%M 을 사용하면 된다.

새롭게 배운 사실

typedef 를 통해서 내가 원하는 모양을 쉽게 사용할 수 있는 자료형으로 만들 수 있었다. 개꿀!!

<정답 코드>

#include<iostream>
#include<vector>
 
using namespace std;
const long long mod = 1000000000;
typedef vector<vector<long long>> matrix;
matrix operator * (matrix a, matrix b)
{
    matrix ret(2, vector<long long>(2));
    
 
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            long long sum = 0;
            for (int m = 0; m < 2; m++)
            {
                sum += ((a[i][m]%mod) * (b[m][j]%mod))%mod;
            }
            ret[i][j] = sum%mod;
        }
    }
 
    return ret;
}
matrix calc(matrix a, long long b)
{
    if (b == 0)
    {
        matrix ret(2, vector<long long>(2));
        ret[0][0] = 1, ret[0][1] = 0, ret[1][0] = 0, ret[1][1] = 1;
        return ret;
    }
    else if (b % 2 == 0)
    {
        matrix temp =calc(a, b / 2);
        return temp*temp;
    }
    else
    {
        matrix temp = calc(a, b - 1);
        return a*temp;
    }
}
int main()
{
    long long a, b;
    long long ans = 0;
    scanf("%lld %lld", &a, &b);
    matrix F(2, vector<long long>(2));
    F[0][0] = 1, F[0][1] = 1, F[1][0] = 1, F[1][1] = 0;
    matrix B = calc(F, b+2);
    matrix A = calc(F, (a-1)+2);
    ans = ((B[0][1] - 1)%mod - (A[0][1] - 1)%mod + mod) % mod;
    
    printf("%lld\n", ans);
 
    return 0;
}