[백준 2086] 피보나치 수의 합

문제 링크 => 2086번: 피보나치 수의 합 (acmicpc.net)

2086번: 피보나치 수의 합

---

수학 + 분할 정복을 이용한 거듭제곱 문제이다.

 

a, b값이 10^18 이라는 점을 고려했을때 logN 을 이용해야 한다는 것을 파악할 수 있다.

 

그래서 Fibo(n) 값을 어떻게 표현해야 효율적인지에 대해서 노가다를 좀 하더니 이러한 결과가 나왔다.

• Fibo(1) = 1
• Fibo(2) = 1
• Fibo(3) = 1^2 + 1^2 = 2 ( Fibo(1)^2 + Fibo(2)^2 ) 
• Fibo(4) = 2^2 - 1^2 = 3 ( Fibo(3)^2 - Fibo(1)^2 )
• Fibo(5) = 1^2 + 2^2 = 5 ( Fibo(2)^2 + Fibo(3)^2 )
• Fibo(6) = 3^2 - 1^2 = 8 ( Fibo(4)^2 - Fibo(2)^2 )
• ...

n % 2 == 1 인경우 => Fibo(n) = Fibo(n/2)^2 + Fibo(n/2+1)^2

n % 2 == 0 인경우 => Fibo(n) = Fibo(n/2+1)^2 - Fibo(n/2-1)^2

 

그리고 a, b가 주어졌을때 Fibo(a)+...+Fibo(b) = Fibo(b+2) - Fibo(a+1) 임을 얻을 수 있다. (이거 또한 노가다)

 

이때 나머지 연산을 통해 값을 1,000,000,000 미만의 0 또는 자연수값으로 표현해야 하는데 주의해야할 점은 딱 2개이다.

1. n % 2 == 0 인경우 Fibo(n) = ( Fibo(n/2+1)^2 - Fibo(n/2-1)^2 + 1,000,000,000 ) % 1,000,000,000 => 임의로 1,000,000,000 을 더하고 나머지 연산을 하는데 이는 음수를 방지하기 위함이다.
2. Result = ( Fibo(b+2) - Fibo(a+1) + 1,000,000,000) % 1,000,000,000 => Fibo(b+2) < Fibo(a+1) 인 경우 음수가 나오는 것을 방지하기 위해 1번과 동일하게 더하고 나머지 연산을 해준다.

마지막으로 map을 활용하여 나왔던 값은 Recursive하게 호출하는 것이 아니라 나왔던 값을 return 하도록 하는 즉, Dynamic Programming 의 Top-Down 방식을 이용하도록 하면 시간초과 없이 패스되는 것을 볼 수 있을 것이다.

---

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'

using namespace std;

map<long long, long long> m[2];

long long fibo(long long x,int idx) {
	if (x == 0) return 0;
	if (x == 1) return 1;
	else if (x == 2) return 1;
	if (m[idx][x]) return m[idx][x];
	if (x % 2 == 0) {
		long long tmp1 = fibo(x / 2 + 1, idx) % 1000000000;
		long long tmp2 = fibo(x / 2 - 1, idx) % 1000000000;
		tmp1 = tmp1 * tmp1 % 1000000000;
		tmp2 = tmp2 * tmp2 % 1000000000;
		return m[idx][x] = (tmp1-tmp2+1000000000) % 1000000000;
	}
	else {
		long long tmp1 = fibo(x / 2, idx) % 1000000000;
		long long tmp2 = fibo(x / 2 + 1, idx) % 1000000000;
		tmp1 = tmp1 * tmp1 % 1000000000;
		tmp2 = tmp2 * tmp2 % 1000000000;
		return m[idx][x] = (tmp1 + tmp2) % 1000000000;
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	long long a,b;
	cin >> a >> b;
	cout << (fibo(b+2,0)-fibo(a+1,1)+1000000000)% 1000000000;

	return 0;
}