[C/C++] 백준 #2086 피보나치 수의 합(분할정복)

이번 문제는 피보나치 수열들의 합을 계산하는 것입니다.  언뜻, 피보나치 수열을 구해서 그 합을 구해야 할 것으로 생각할 수 있습니다.  수학식을 유도하는 것이 어려워서인지, 문제의 난이도는 Gold I 단계입니다.

 

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

2086번: 피보나치 수의 합

 

조금 생각해보면, 이 수열도 피보나치 수열과 다르지 않다는 것을 알 수 있습니다.  수학적으로 점화식을 이용해서 풀이를 하는 것이라서, 다소 생소할 수가 있습니다.

 

피보나치 수열은 다음과 같죠.

\[ f(0) = 0, f(1) = 1\]

\[f(n) = f(n-1)+f(n-2) \]

 

피보나치의 n번째 항을 구하는 프로그램은 간단한 형태의 재귀함수로 풀 수도 있고, 반복문을 이용해서 풀 수도 있습니다.

 

그러면 1항부터 n항까지의 합은 어떻게 표현할 수 있을까요?

\[  F(1) = 1, F(2) = 2 \]

\[ F(n) = \sum_{k=1}^{n} f(k) = f(1) + \sum_{k=2}^{n} f(k) = 2\sum_{k=1}^{n-2} f(k) + f(n-1) + f(1) \]

형태가 됩니다.  그러면 \(\sum\) 부분을 적절하게 조절하면,

\[ F(n) = F(n-2) + F(n-1) + 1 \]

이 됩니다.

 

피보나치 수열이 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 형태이니,

피보나치 수열의 합은 1, 2, 4, 7, 12, 20, 33, 54, 88, 143, ... 형태가 됩니다.

 

그런데, +1이 붙은 것때문에, 조금 수정을 할 필요가 있습니다.  \( S(n) = F(n) + 1 \) 로 규정을 하는 것이죠.  그러면, 위의 식은 다음과 같이 변경됩니다.

 

\[ S(n) = S(n-1) + S(n-2) \]

이러면 피보나치 수열과 똑같은 점화식을 얻을 수 있습니다.  초기값은

\[ S(1) = 2, S(2) = 3 \rightarrow S(0) = 1, S(1) = 2 \]

이 됩니다.

 

이렇게 해도 문제는 남습니다.  n이 너무 큽니다.  그래서 저는 행렬을 사용했습니다.  행렬을 사용하면, 행렬의 제곱을 재귀적으로 이용해서 \( O(\log n) \)의 곱셈과 덧셈을 하면 됩니다.

 

제가 작성한 소스입니다.

//----------------------------------------------------------
//    baekjoon #2086 - Sum of Fibonacci Numbers
//        - by Aubrey Choi
//        - created at 2020-02-08
//----------------------------------------------------------
#include <stdio.h>
#define    MOD    1000000000

void mult(long long a[], const long long b[])
{
    long long r0 = (a[0] * b[0] + a[1] * b[2]) % MOD;
    long long r1 = (a[0] * b[1] + a[1] * b[3]) % MOD;
    long long r2 = (a[2] * b[0] + a[3] * b[2]) % MOD;
    long long r3 = (a[2] * b[1] + a[3] * b[3]) % MOD;
    a[0] = r0, a[1] = r1, a[2] = r2, a[3] = r3;
}
long long sum(long long n)
{
    long long p[4]={1,1,1,0}, c[4]={1,0,0,1};
    for(;n;n>>=1)
    {
        if(n&1) mult(c,p);
        mult(p,p);
    }
    return (c[2]*2+c[3]+MOD-1)%MOD;
}
int main()
{
    long long a, b;
    scanf("%lld%lld",&a,&b);
    printf("%lld\n", (sum(b)-sum(a-1)+MOD)%MOD);
}