[BaekJoon][11444] 피보나치 수 6

BAEKJOON ONLINE JUDGE

11444 피보나치 수 6

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

input이 매우 크기 때문에 그냥 구할 수 없다.

피보나치 행렬과 제곱의 이진수 응용을 이용해서 구해야 한다.

#include <stdio.h>
#include <vector>
using namespace std;
 
#define Namuge    1000000007
 
vector<vector<long long int>> multipleMatrix
(vector<vector<long long int>> &first, vector<vector<long long int>> &second)
{
    long long int t;
    long long int temp;
    vector<vector<long long int>> ans(2, vector<long long int>(2));
 
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            temp = 0;
            for (int k = 0; k < 2; k++) 
                temp += first[i][k] * second[k][j];
            ans[i][j] = temp % Namuge;
        }
    }
    return ans;
}
 
vector<vector<long long int>> powMatrix
vector<vector<long long int>> &matrix, long long int m)
{
    vector<vector<long long int>> ans(2, vector<long long int>(2));
    vector<vector<long long int>> mt = matrix;
 
    ans[0][0] = ans[1][1] = 1;
 
    while (m > 0) {
        if (m % 2)    ans = multipleMatrix(ans, mt);
        mt = multipleMatrix(mt, mt);
        m /= 2;
    }
    return ans;
}
 
int main()
{
    long long int n;
    vector<vector<long long int>> vec(2, vector<long long int>(2));
    vec[0][0] = vec[0][1] = vec[1][0] = 1;
    vec[1][1] = 0;
 
    scanf("%lld", &n);
 
    vec = powMatrix(vec, n - 1);
 
    printf("%d\n", vec[0][0]);
 
    return 0;
}