백준 2086 피보나치 수의 합 C++

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

2086번: 피보나치 수의 합

a번째부터 b번째까지 피보나치 수열의 합을 구하는 문제입니다.

 

피보나치 수열의 합은 생각해본 적이 없었는데 식은 간단했습니다.

F(1)=1, F(2)=1 인 피보나치 수열의 합은 다음과 같습니다.

 

S(n) = F(1) + ... + F(n) = F(n+2) - 1 

 

그리고 피보나치 수열은 아래와 같이 행렬로 표현이 가능합니다.

 

그러므로 거듭제곱 연산 시 900.... 에 해당하는 최대 제곱 연산을 수행하는 것이 아닌, 이진수로 변환 후 거듭제곱을 진행하면 됩니다.

 

예를 들어, a^13 = a^(1101) 을 계산하려고 하면 1=a^0을 시작으로 이진수의 앞에서부터 

1이 존재하면 제곱 후 a를 곱하고, 0이 존재하면 제곱 연산만 수행하면 됩니다.

첫번째 비트가 1이므로 (a^0)^2 * a = a

두번째 비트가 1이므로 a^2 * a = a^3

세번째 비트가 0이므로 (a^3)^2 = a^6

네번째 비트가 1이므로 (a^6)^2 * a = a^13 입니다.

 

이를 행렬 거듭제곱에도 동일하게 적용하면 F(n+2) 를 O(log n) 으로 효율적으로 구할 수 있고, 피보나치 수열의 합도 효율적으로 구할 수 있습니다.

a번째부터 b번째까지 합이므로 S(b) - S(a-1) 을 구하면 됩니다.

 

코드는 아래와 같습니다.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// 피보나치 수열 합 S(n) = F(n+2) - 1
// F(1)=F(2)=1
// 피보나치 수열 행렬 표현
// (F(n+1), F(n)) = ((1 1) (1 0))^n * (1 0)

long long mod = 1000000000;

string binary(long long n) {
  // bin(n)
  string bin = "";
  while(n > 0) {
    bin += (n & 1) + '0';
    n >>= 1;
  }
  reverse(bin.begin(), bin.end());
  return bin;
}

pair<pair<long long, long long>, pair<long long, long long>> mul(pair<pair<long long, long long>, pair<long long, long long>>A, pair<pair<long long, long long>, pair<long long, long long>>B) {
  // A*B
  // mat : ((x11 x12) (x21 x22))
  pair<pair<long long, long long>, pair<long long, long long>> res = {{0, 0}, {0, 0}};

  res.first.first = (A.first.first * B.first.first + A.first.second * B.second.first) % mod;
  res.first.second = (A.first.first * B.first.second + A.first.second * B.second.second) % mod;
  res.second.first = (A.second.first * B.first.first + A.second.second * B.second.first) % mod;
  res.second.second = (A.second.first * B.first.second + A.second.second * B.second.second) % mod;
  return res;
}

pair<long long, long long> power(long long p) {
  string bin_p = binary(p);

  pair<pair<long long, long long>, pair<long long, long long>> mat = {{1, 1}, {1, 0}};
  pair<pair<long long, long long>, pair<long long, long long>> baseMat = {{1, 1}, {1, 0}};
  
  for(int i = 1; i < bin_p.size(); i++) {
    // 제곱 후 곱셈
    mat = mul(mat, mat);
    if(bin_p[i] == '1') {
      mat = mul(mat, baseMat);
    }
  }

  // (1, 0) 곱하기
  pair<long long, long long> res = {0, 0};
  res.first = mat.first.first;
  res.second = mat.second.first;
  return res;
}

long long sum(long long n) {
  // F(1) ~ F(n) 까지 합 = S(n) = F(n+2) - 1
  long long pow = n + 1;

  pair<long long, long long> mat = power(pow);
  long long Sn = mat.first - 1LL;
  return Sn;
}

int main() {
  long long a, b;
  cin >> a >> b;
  if(a == 1LL) {
    cout << sum(b);
    return 0;
  }
  
  long long Sa = sum(a - 1);
  long long Sb = sum(b);
  long long res = Sb - Sa;
  if(res < 0) {
    res += mod;
  }
  cout << res;
}