$\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;
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준/C,C++] 2261번: 가장 가까운 두 점 (0) | 2021.03.29 |
---|---|
[백준/C,C++] 6549번: 히스토그램에서 가장 큰 직사각형 (0) | 2021.03.28 |
[백준/C,C++] 10830번: 행렬 제곱 (0) | 2021.03.26 |
[백준/C,C++] 2740번: 행렬 곱셈 (0) | 2021.03.26 |
[백준/C,C++] 11401번: 이항 계수 3 (0) | 2021.03.26 |
댓글