[11444] 피보나치 수 6

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

11444번: 피보나치 수 6

<문제>

"[2749] 피보나치 수 3" 은 모듈러가 작아서 피사노주기를 이용해 꽤나 간단하게 해결이 가능했지만,

모듈러가 커지면 행렬의 거듭제곱으로 O(logN)의 복잡도를 갖는다.

a^b mod c의 값을 logN만에 구하던 것과 매우 유사하다. 단지 수 하나가 2by2 행렬로 바뀐것 뿐이다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007;
typedef struct {
    ll arr[2][2];
} M;
M base;
ll n;
M mul(M A, M B) {
    M ret;
    ret.arr[0][0] =
        (A.arr[0][0] * B.arr[0][0] + A.arr[0][1] * B.arr[1][0]) % MOD;
    ret.arr[0][1] =
        (A.arr[0][0] * B.arr[0][1] + A.arr[0][1] * B.arr[1][1]) % MOD;
    ret.arr[1][0] =
        (A.arr[1][0] * B.arr[0][0] + A.arr[1][1] * B.arr[1][0]) % MOD;
    ret.arr[1][1] =
        (A.arr[1][0] * B.arr[0][1] + A.arr[1][1] * B.arr[1][1]) % MOD;
    return ret;
}
M f(M cur, ll p) {
    if (p <= 1) return cur;
    cur = f(cur, p / 2);
    cur = mul(cur, cur);
    if (p & 1) cur = mul(cur, base);
    return cur;
}
int main(void) {
    base.arr[0][0] = 1;
    base.arr[0][1] = 1;
    base.arr[1][0] = 1;
    base.arr[1][1] = 0;
    cin >> n;
    M res = f(base, n);
    cout << res.arr[0][1];
    return 0;
}