문제

아이디어

피보나치 함수를 $F(x)$로 정의할 때, $S(n) = \sum_{i=1}^{n} F(i)$라 하자.
이 때, $F(x) = F(x+2) - F(x+1)$이므로, 아래 수식이 성립한다.

$S(n) = F(1) + F(2) + ... + F(n)$
$=(F(3) - F(2)) + (F(4) - F(3)) + ... + (F(n+2)-F(n+1))$
$=F(n+2) - 1$

즉, 주어진 문제는 아래와 같이 표현할 수 있다.

$F(a) + F(a+1) + ... + F(b)$
$=S(b) - S(a-1)$
$=F(b+2) - F(a+1)$

하지만 a와 b가 매우 큰 수 (1 ≤ a ≤ b ≤ 9,000,000,000,000,000,000)이므로 아래의 피보나치 함수의 특징을 적용한 분할 정복을 통해 구할 수 있다.

$F(m+n) = F(m)F(n+1) + F(m-1)F(n)$ 이 성립하므로,

$(1)\; m = n = k \text{ 일 때,}$

$F(2k) = F(k)\bigl(2F(k+1) - F(k)\bigr)$

$(2)\; m = k+1,\; n = k \text{ 일 때,}$

$F(2k+1) = F(k+1)^2 + F(k)^2$

소스코드

import java.io.*;
import java.util.*;

public class Main {
    static long a, b;
    static final long MOD = 1000000000;
    static Map<Long, Long> fiboMap;

    static long mulMod(long x, long y) {
        return (x % MOD) * (y % MOD) % MOD;
    }

    static long getFibonacci(long x) {
        if (fiboMap.containsKey(x))
            return fiboMap.get(x);

        long res = -1L;

        if ((x & 1) == 0) {
            long half = getFibonacci(x >> 1);
            long halfPlusOne = getFibonacci((x >> 1) + 1);

            long t = ((2 * halfPlusOne % MOD - half + MOD) % MOD);
            res = mulMod(half, t);
        } else {
            long p = getFibonacci((x + 1) >> 1);
            long m = getFibonacci((x - 1) >> 1);
            res = (mulMod(p, p) + mulMod(m, m)) % MOD;
        }


        if (res > MOD) res %= MOD;
        fiboMap.put(x, res);
        return res;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        a = Long.parseLong(st.nextToken());
        b = Long.parseLong(st.nextToken());
        fiboMap = new HashMap<>();

        fiboMap.put(0L, 0L);
        fiboMap.put(1L, 1L);
        fiboMap.put(2L, 1L);

        long ans = getFibonacci(b + 2) - getFibonacci(a + 1);
        if (ans < 0) ans += MOD;

        System.out.println(ans);
    }
}

채점결과

long ans = getFibonacci(b + 2) - getFibonacci(a + 1);
if (ans < 0) ans += MOD;

위처럼 결과과 음의 값을 가질 때 보상해주지 않는다면 오답이 될 수 있으니 주의하자.