백준 2086 피보나치 수의 합

www.acmicpc.net/problem/2086

2086번: 피보나치 수의 합

a번째 피보나치 수~b번째 피보나치 수의 합을 구하는 문제다.

a부터 b까지 모든 피보나치 수의 합을 하나씩 구해서 더하면 O(N) 이므로 a가 1이고 b가 9e18 일 경우 무조건 시간 초과... 따라서 간단한 관찰을 통해 식을 구해야 한다.

1부터 10까지 전부 적어보면

1   2   3   4   5   6   7   8   9   10

1   1   2   3   5   8   13  21 34  55

인데 \(F_5\) 부터 \(F_7\) 까지 구해보면 합은 26이고

이는 \(F_9-F_6\) 인 것을 알 수 있다.

 

일반화해보면

$$F_{a \;to\; b} = F_{b+2} - F_{a+1}$$ 

인 것을 확인할 수 있다.

 

또한 A와 B가 빼줄 때 음수 값이 나올 수 있으므로 

((A % MOD) - (B % MOD) + MOD) % MOD로 처리해 줘야 한다.

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const int MOD = 1e9;
#define vii vector<vector<ll>>
#define vi vector<ll>

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

vii operator* (const vii& a, const vii& b) {
	ll sz = a.size();
	vii ret(sz, vi(sz));
	for (ll i = 0; i < sz; i++) {
		for (ll j = 0; j < sz; j++) {
			for (ll k = 0; k < sz; k++) {
				ret[i][j] += a[i][k] * b[k][j];
			}
			ret[i][j] %= MOD;
		}
	}
	return ret;
}

vii power(vii a, ll b) {
	ll sz = a.size();
	vii ret(sz, vi(sz));
	for (ll i = 0; i < sz; i++) ret[i][i] = 1;

	while (b) {
		if (b % 2) ret = ret * a;
		b /= 2;
		a = a * a;
	}
	return ret;
}

int main() {
	ll n, m;
	cin >> n >> m;
	vii A = { {1,1},{1,0} };
	vii a = power(A, n + 1);
	vii b = power(A, m + 2);
	ll ans = (b[0][1] % MOD - a[0][1] % MOD + MOD) % MOD;
	cout << ans << endl;

	return 0;
}