본문 바로가기
알고리즘/백준

[백준/C,C++] 11444번: 피보나치 수 6

by 이민훈 2021. 3. 26.

www.acmicpc.net/problem/11444

 

11444번: 피보나치 수 6

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

www.acmicpc.net

hackids.tistory.com/56

 

[백준/C,C++] 10830번: 행렬 제곱

www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출

hackids.tistory.com

$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_n+1 & F_n \\ F_n & F_n-1 \end{bmatrix}$ 임을 이용하여 문제를 해결할 수 있습니다.

 

n은 매우 큰 값이 들어올 수 있으므로 분할정복을 통한 행렬 거듭제곱이 힌트입니다.

 

#include<iostream>

using namespace std;

const int MOD = 1000000007;
const int MAX = 2;

using ll = long long;
using Matrix = struct {
    ll mat[MAX][MAX];
};

ll n, b;

Matrix operator*(const Matrix& a, const Matrix& b)
{
    Matrix tmp;
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            tmp.mat[i][j] = 0;
            for (int k = 0; k < MAX; k++) {
                tmp.mat[i][j] += a.mat[i][k] * b.mat[k][j];
            }
            tmp.mat[i][j] %= MOD;
        }
    }
    return tmp;
}

Matrix power(const Matrix& m, ll num)
{
    if (num == 1) return m;
    if (num % 2 != 0) {
        return power(m, num - 1) * m;
    }
    Matrix half = power(m, num / 2);
    return half * half;
}

int main(void)
{
    cin >> n;

    Matrix m;
    m.mat[0][0] = 1;
    m.mat[0][1] = 1;
    m.mat[1][0] = 1;
    m.mat[1][1] = 0;

    m = power(m, n);
    
    cout << m.mat[0][1] % MOD;

    return 0;
}

댓글