[1086] 피보나치 수의 합

문제 출처 : https://www.acmicpc.net/problem/1086

분류 : 수학

백준 1086 피보나치 수의 합

큰 범위의 피보나치 수의 합을 구하라

---

구현 포인트

1) 피보나치 행렬표현을 이용 (O(logN))

2) 피보나치 수의 합을 수식으로 구하기

이 문제는 피보나치 수에 대해 공부하면서 2)를 망각하고 있었기에 남기기로 했다.

1)과 2)에 대한 내용은 링크에 있다.

코드는 아래와 같다.

#include<cstdio>
#include<vector>
#define mod 1000000000
 
using namespace std;
typedef vector<vector<long long> > matrix;
 
matrix operator*(const matrix&a, const matrix&b) {
    int n = a.size();
    matrix c(n, vector<long long>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                c[i][j] += a[i][k] * b[k][j];
            }
            c[i][j] %= mod;
        }
    }
    return c;
}
 
int main() {
    long long a, b;
    matrix E = { {1, 0}, {0, 1} };
    matrix A(E), B(E);
    matrix X = { {1, 1},{1, 0} };
    scanf("%lld %lld", &a, &b);
    a += 1; b += 2;
    while (a) {
        if(a%2){
            A = A*X;
        }
        X = X*X;
        a /= 2;
    }
    X = { { 1, 1 },{ 1, 0 } };
    while (b) {
        if (b % 2) {
            B = B*X;
        }
        X = X*X;
        b /= 2;
    }
    printf("%lld\n", (B[0][1]-A[0][1]+mod)%mod);
    return 0;
}