본문 바로가기

알고리즘 관련/BOJ

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

문제: icpc.me/11443


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


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


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


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)13213 Binary Roads  (0) 2017.10.16
BOJ)11442 홀수번째 피보나치 수의 합  (0) 2017.10.14
BOJ)5883 아이폰 9S  (0) 2017.10.13
BOJ)5542 JOI 국가의 행사  (0) 2017.09.12
BOJ)13330 유사 팰린드롬  (0) 2017.09.08