백준 알고리즘 2086번 : 피보나치 수의 합

링크

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

sol1) 행렬 + 빠른 거듭제곱 알고리즘

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int int64_t
using namespace std;

using ll = long long;
using matrix = vector<vector<ll>>;

const int MOD = 1e9;

matrix I = {{1, 0}, {0, 1}};
matrix base = {{1, 1}, {1, 0}};

matrix matrix_mul(matrix a, matrix b)
{
    return {
        {((a[0][0] * b[0][0]) % MOD + (a[0][1] * b[1][0]) % MOD) % MOD, ((a[0][0] * b[0][1]) % MOD + (a[0][1] * b[1][1]) % MOD) % MOD},
        {((a[1][0] * b[0][0]) % MOD + (a[1][1] * b[1][0]) % MOD) % MOD, ((a[1][0] * b[0][1]) % MOD + (a[1][1] * b[1][1]) % MOD) % MOD}};
}

matrix _pow(matrix x, int n)
{
    matrix ret = I;
    while (n)
    {
        if (n & 1)
            ret = matrix_mul(ret, x);
        n /= 2;
        x = matrix_mul(x, x);
    }
    return ret;
}

int32_t main()
{
    fastio;
    int a, b;
    cin >> a >> b;
    cout << (_pow(base, b + 2)[0][1] % MOD - _pow(base, a - 1 + 2)[0][1] % MOD + MOD) % MOD << '\n';
}