2016.06.02 모임 56

모임 공지

  • 활동 일시: 06월 02일 (목) 19:02
  • 모임 장소: 하이퍼 커넥트 14층
  • 내용 : coder’s high, fibonacci sequence
  • 샌드위치 형성

장소는 이곳을 참고 하세요

coder’s high 2016

fibonacci sequence

피보나치 일반항은 지수 식으로 표현된다.
그래서 O (log n) 시간에 n 번째 항을 구할 수 있다.

typedef vector<long long> matrix;

const int M = 1000000007;

matrix operator * (const matrix &a, const matrix &b) {
    matrix c(4);
    c[0] = (a[0] * b[0] + a[1] * b[2]) % M;
    c[1] = (a[0] * b[1] + a[1] * b[3]) % M;
    c[2] = (a[2] * b[0] + a[3] * b[2]) % M;
    c[3] = (a[2] * b[1] + a[3] * b[3]) % M;
    return c;
}

int fibonacci(int n) {
    if (n <= 1) return n;

    matrix r = {1, 0, 0, 1};
    matrix m = {1, 1, 1, 0};

    while (0 < n) {
        if (n & 1) {
            r = r * m;
        }
        m = m * m;
        n >>= 1;
    }

    return r[1];
}

사진

사진 사진


Written on May 27, 2016