[백준] 11440 - 피보나치 수의 제곱의 합 C++

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

11440번: 피보나치 수의 제곱의 합

n이 주어졌을 때, 0번째 피보나치 수의 제곱부터 n번째 피보나치 수의 제곱을 합한 값을 구하는 문제다.

피보나치 수의 성질에 대한 문제로, 모든 피보나치수를 구해 제곱을 더할 수 없기 때문에 주어진 식에 대한 유도가 필요하다.

 

피보나치 수 일반항은 다음과 같다.

n 대신 n-1 을 대입하고, Fn 에 대한 식으로 정리한다.

이를 구해야 할 식에 대입한다. Fn 과 Fn+1 를 구하면 n 번째까지 피보나치수의 제곱의 합을 구할 수 있다. 

주어진 n이 1,000,000,000,000,000,000 보다 작거나 같은 자연수이므로 DP 로 O(n) 으로 풀이할 시 시간초과가 발생한다. 따라서 분할 정복을 이용한 거듭제곱으로 O(log(n)) 으로 풀이해야 한다.  

 

거듭제곱을 이용하기 위해 행렬식을 이용한 행렬 멱법을 이용한다. 행렬 멱법은 점화식을 행렬화시켜 풀이하는 방법이다. 

편의를 위해 2X2 행렬끼리의 곱으로 나타내보자.  첫 번째 행렬이 구하고자 하는 값이고, 두 번째 행렬이(A) 거듭제곱으로 이용할 행렬, 세 번째 행렬이(I) 초기항 행렬이다. 행렬의 요소를 인덱스로 얻을 수 있으므로 F2 = (A x I)[0][0], F1 = (A x I)[1][0] 가 된다.

이를 일반화 시켜보면 다음을 얻을 수 있다.

따라서 Fn 과 Fn+1 을 분할정복을 이용해 구하고, 둘을 곱해주면 된다.

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;
using vl = vector<ll>;
using vll = vector<vl>;

#define MAX 2
#define MOD 1000000007
#define endl '\n'

ll n;
vll operator*(vll &a, vll &b) {
    vll ret(MAX, vl(MAX));
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            for (int k = 0; k < MAX; k++) {
                ret[i][j] = (ret[i][j] + a[i][k] * b[k][j]) % MOD;
            }
        }
    }
    return ret;
}

// n 번째 피보나치수를 반환
ll power(ll n) {
    vll A = {{1, 1}, {1, 0}};
    vll I = {{1, 0}, {0, 0}};
    while (n) {
        if (n % 2)
            I = A * I;
        A = A * A;
        n /= 2;
    }
    return I[1][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    ll ans = (power(n) * power(n + 1)) % MOD;
    cout << ans << endl;
    return 0;
}