티스토리 뷰

알고리즘/BOJ

BOJ 11444, 피보나치 수 6

아테즈 2018. 10. 20. 20:47
이 문제는 A(n) = A(n-1) + A(n-2)의 선형 점화식의 항을 빠르게 구하는 것을 목표로 합니다. 게다가 n의 범위가 10^18(1,000,000,000,000,000,000)인 걸 보아 절대 동적 계획법으로는 풀 수 없는 문제입니다. 
이럴 땐, 점화식을 자세히 살펴보고, 분해해보아야 합니다.

수열의 n번째 항과, n-1번째 항을 위 아래로 나열해보면
 
과 같이 나타낼 수 있습니다. 그럼? 이것을 행렬로 나타내보면? 

 
입니다. 오! 개쩔죠? 그럼? 이 점화식을 계속해서 나열해본다면!

이 될 것이고

이렇게 되니까, 피보나치 수열의 일반 행렬을 얻을 수 있습니다.

n by n의 행렬을 곱하는 데엔 보통 O(n^3)의 시간 복잡도가 필요합니다.
그리고 같은 행렬을 M번 곱하는 데는 O(Mn^3)의 시간이 필요하죠. 하지만, 문제에서 요구하는 t의 범위가 20억 (2*10^9)이니 위의 시간복잡도로 풀기엔 아직도 턱없이 부족합니다.

그러므로, 위에 서술한대로 시간 복잡도를 O(N^3logM)으로 줄이기 위해선, 어떤 수의 거듭제곱을 빠르게 구하는 알고리즘인 Fast Power Algorithm을 사용해야합니다.

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
39
40
41
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
typedef vector<vector<long long>> matrix;
const LL mod = 1000000007;
 
matrix operator* (const matrix &a, const matrix &b) {
    int n = a.size();
    matrix c(n, vector<long long>(n));
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            for (int k = 0; k<n; k++) {
                c[i][j] += a[i][k] * b[k][j];
            }
            c[i][j] %= mod;
        }
    }
    return c;
}
 
int main() {
    LL n;
 
    cin >> n;
 
    matrix ans = { { 10 },{ 01 } };
    matrix a = { { 11 },{ 10 } };
 
    while (n > 0) {
        if (n % 2 == 1) {
            ans = ans * a;
        }
        a = a * a;
        n /= 2;
    }
 
    cout << ans[0][1];
 
    return 0;
}

cs


댓글
댓글쓰기 폼
공지사항
Total
21,753
Today
15
Yesterday
12
링크
TAG
more
«   2022/08   »
  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      
글 보관함