BOJ)11443 짝수번째 피보나치 수의 합

문제: icpc.me/11443

N보다 작은 모든 짝수번째 피보나치 수의 합을 구하는 문제이다.

N이 너무 크기 때문에 피보나치 수의 N번째 항은 행렬 곱셈의 분할 정복으로 log 시간에 구할 수 있지만 이 방법으로 모든 피보나치 수를 구하는건 너무 많은 시간이 걸린다.

하지만 수를 쭉 나열해보면 Rn 이 n보다 작은 모든 짝수번째 피보나치 수의 합이라고 가정한다면

R(2n)=R(2n+1)=F(2n+1)-1 이라는 공식이 나온다.

따라서 이에 대한 답을 구해주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mx;
const ll MOD = (ll)(1e9 + 7);
mx operator *(const mx &x, const mx &y) {
    int n = x.size();
    mx z(n, vector<ll>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                z[i][j] += x[i][k] * y[k][j];
                z[i][j] %= MOD;
            }
        }
    }
    return z;
}
ll n;
int main() {
    scanf("%lld", &n);
    if (n <= 1) {
        printf("%lld\n", n);
        return 0;
    }
    mx a = { {1,0},{0,1} };
    mx b = { {1,1},{1,0} };
    while (n > 0) {
        if (n % 2)
            a = a*b;
        b = b*b;
        n /= 2;
    }
    printf("%lld\n", a[0][1]);
    return 0;
}