BOJ)11442 홀수번째 피보나치 수의 합

문제: icpc.me/11442

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

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

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

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

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

#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mx;
const ll mod = 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 % 2)n++;
    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;
}