백준) 피보나치 수 3

피보나치 수 3

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

피보나치 수열은 다음과 같다.

0, 1, 1, 2, 3, 5, ...

n이 long long 범위 안으로 주어질 때 n번 째 피보나치 수를 구해라.

앞의 두 수를 더하면 피보나치 수가 생긴다. 하지만 n이 long long 범위이기 때문에 시간안에 구할 수 없다.

새로운 방법은 행렬을 사용하는 것이다.

f(n) = f(n-1) + f(n-2) // f(n-1) = f(n-1) 이므로,

여전히 행렬을 n-1번 곱해서 각 성분을 알야내야 한다는 점에서 시간복잡도는 줄지 않았다.

하지만 행렬이 곱셉에서 결합법칙이 성립한다는 점을 떠올린다면,

예를 들어 R^7 = R^4 * R^2 * R^1 로 분해할 수 있다는 것을 알 수 있다.

n-1은 long long 범위이므로 최대 2^64까지 커진다. 따라서 미리 2^0, 2^1, ... 2^63 까지 R의 제곱들을 구해놓으면,

log(n)시간에 답을 구할 수 있다. 위와 같이 4,2,1 제곱을 가져다 곱해주기만 하면 되기 때문이다.

소스는 다음과 같다.

#include <stdio.h>
#define mod 1000000
long long dp[64][2][2];
long long mat[2][2] = { {1ll,0ll},{0ll,1ll} };
long long n;
 
int main() {
    scanf("%lld", &n);
    if (n == 0) {
        printf("0");
        return 0;
    }
 
    if (n == 1) {
        printf("1");
        return 0;
    }
 
    dp[0][0][0] = 1ll, dp[0][0][1] = 1ll;
    dp[0][1][0] = 1ll, dp[0][1][1] = 0ll;
 
    for (int i = 1; i < 64; ++i) {
        dp[i][0][0] =
            ((dp[i - 1][0][0] * dp[i - 1][0][0]) % mod +
            (dp[i - 1][0][1] * dp[i - 1][1][0]) % mod) % mod;
        dp[i][0][1] =
            ((dp[i - 1][0][0] * dp[i - 1][0][1]) % mod +
            (dp[i - 1][0][1] * dp[i - 1][1][1]) % mod) % mod;
        dp[i][1][0] =
            ((dp[i - 1][1][0] * dp[i - 1][0][0]) % mod +
            (dp[i - 1][1][1] * dp[i - 1][1][0]) % mod) % mod;
        dp[i][1][1] =
            ((dp[i - 1][1][0] * dp[i - 1][0][1]) % mod +
            (dp[i - 1][1][1] * dp[i - 1][1][1]) % mod) % mod;
    } // 행렬의 2^i 제곱을 미리 구해놓는다.
 
 
    n--;
    for (int i = 0; (1ll << i) <= n; ++i) {
        if ((n & (1ll << i)) != 0) {
            long long tmp[2][2];
            for (int a = 0; a < 2; ++a)
                for (int b = 0; b < 2; ++b)
                    tmp[a][b] = mat[a][b];
 
            mat[0][0] =
                ((tmp[0][0] * dp[i][0][0]) % mod +
                (tmp[0][1] * dp[i][1][0]) % mod) % mod;
            mat[0][1] =
                ((tmp[0][0] * dp[i][0][1]) % mod +
                (tmp[0][1] * dp[i][1][1]) % mod) % mod;
            mat[1][0] =
                ((tmp[1][0] * dp[i][0][0]) % mod +
                (tmp[1][1] * dp[i][1][0]) % mod) % mod;
            mat[1][1] =
                ((tmp[1][0] * dp[i][0][1]) % mod +
                (tmp[1][1] * dp[i][1][1]) % mod) % mod;
        }
    }
 
    printf("%lld\n", mat[0][0]);
 
    return 0;
}