[C++] 11440번 피보나치 수의 제곱의 합 / 28749번 Квадраты Фибоначчи

 

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

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

---

 

25/03/04

25/03/09

 

 

두 문제는 인덱스만 다르고 동일한 문제이므로, 같은 풀이 방법으로 설명하겠다.

---

 

문제 접근 방식:

 

 

피보나치 수의 거듭 제곱의 합을 구하는 문제이다.

 

$F_{n} = F_{n-1} + F_{n-2}$를 생각해보자.

 

제곱을 하면 다음과 같다.

 

$$\begin{align}{F_{n}}^{2} &= (F_{n-1} + F_{n-2})^{2} \\ &= {F_{n-1}}^{2} + {F_{n-2}}^{2} + 2F_{n-1}F_{n-2}\end{align}$$

 

제곱 항은 공통이 되는데, 뒤에 붙은 $2F_{n-1}F_{n-2}$항이 공통이 되지 않는다.

 

편의 상 ${F_{n}}^2 = G_{n}$이라고 하고, $F_{n-1}F_{n-2} = H_{n-2}$라고 해보자.

 

그러면 식이 다음과 같이 정리된다.

 

$$G_{n} = G_{n-1} + G_{n-2} + 2H_{n-2}$$

 

행렬 거듭제곱으로 풀려면 $H_{n-2}$와 $H_{n-1}$간의 관계를 알아야 하는데, 생각해보자.

 

$$\begin{align}H_{n-1} &= F_{n}F_{n-1} \\ &= (F_{n-1} + F_{n-2})F_{n-1} \\ &= {F_{n-1}}^{2} + F_{n-1}F_{n-2} \\ &= G_{n-1} + H_{n-2}\end{align}$$

 

위에 식에 따르면 아주 잘 정리가 될 것이다.

 

따라서, $G$와 $H$의 관계를 행렬로 적으면 다음과 같이 적을 수 있다.

 

$$\begin{bmatrix}G_{n} \\ G_{n-1} \\ H_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 & 2 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \end{bmatrix} \begin{bmatrix} G_{n-1} \\ G_{n-2} \\ H_{n-2} \end{bmatrix}$$

 

편의 상 숫자로 이뤄진 행렬을 $A$라고 하자.

 

우리는 $G_{1} + G_{2} + G_{3} + \cdots + G_{n}$의 값을 구해야 한다. 어떻게 할 것인가? ($G_{0} = 0$이기 때문에 편의상 저렇게 적었다.)

 

예를 들어, 우리가 $G_{4}$의 값을 구해야 한다고 쳐보자.

 

그러면, 다음과 같은 식을 쓸 수 있을 것이다.

 

$$\begin{align}\begin{bmatrix}G_{4} \\ G_{3} \\ H_{3} \end{bmatrix} &= A \begin{bmatrix} G_{3} \\ G_{2} \\ H_{2} \end{bmatrix} \\ &= A^{2} \begin{bmatrix} G_{2} \\ G_{1} \\ H_{1} \end{bmatrix} = A^{2} \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} \\ G_{4} &= \text{sum of }A^{2}\text{ first row}\end{align}$$ 

 

즉, 일반화를 하자면, $G_{n}$의 값을 구하기 위해서는 $A^{n-2}$의 첫번째 행을 전부 더한 값을 구해야 한다.

 

따라서, $G_{1} + G_{2} + G_{3} + \cdots + G_{n}$의 값을 구하는 것은 다음을 구하는 것과 같다.

 

$$1 + \text{sum of }(I + A + \cdots + A^{n-2})\text{ first row}$$

 

그러면 $I + A + \cdots + A^{n-2}$는 어떻게 빨리 구할 것인가?

 

편의 상 $A + A^{2} + \cdots + A^{n-2}$를 빨리 구하는 문제로 바꾸자. 어차피 이 해당 행렬에서 $I$을 더해주면 그게 그 값이다.

 

$S_{i} = A + A^{2} + \cdots + A^{i}$라고 정의하자. 우리가 구하고 싶은 것은 $S_{n-2}$가 되는 것이다.

 

그러면 $S_{i}$를 어떻게 빨리 구할 것이냐?가 결국 관건인데, 이는 분할 정복의 아이디어를 통해 빠르게 구할 수 있다.

 

$i$가 짝수라면, $S_{i} = A + A^{2} + \cdots + A^{i/2} + A^{i/2 + 1} + \cdots + A^{i} = S_{i/2} + A^{i/2}S_{i/2} = S_{i/2}(I + A^{i/2})$가 성립한다.

 

$i$가 홀수라면, 비슷하게 $S_{i} = S_{i/2}(I + A^{i/2}) + A^{i}$가 성립한다.

 

이를 이용하면 $S_{n-2}$를 빠르게 구할 수 있고, 이를 통해 우리가 구하고자 하는 값을 충분히 빠른 시간에 구할 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 11440번 피보나치 수의 제곱의 합
// 분할정복을 이용한 거듭제곱
/*
접근 방법:
Fn^2 = (F_{n-1} + F_{n-2})^2 = F_{n-1}^2 + F_{n-2}^2 + 2F_{n-1}F_{n-2};
F_{n}^2 = G_{n}, F_{n-1}F_{n-2} = H_{n-2}

G_n       1 1 2 G_{n-1}
G_{n-1} = 1 0 0 G_{n-2}
H_{n-1}   1 0 1 H_{n-1}

행렬 거듭제곱 + 행렬 거듭제곱의 합으로 분할정복 GOGO
*/

#include <iostream>
#include <vector>
#include <map>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
typedef long long ll;
#define MOD 1000000007

vector<vector<ll>> A = {
    {1, 1, 2},
    {1, 0, 0},
    {1, 0, 1}
};
vector<vector<ll>> I = {
    {1, 0, 0},
    {0, 1, 0},
    {0, 0, 1}
};
map<ll, vector<vector<ll>>> DP_S;
map<ll, vector<vector<ll>>> DP_A;

vector<vector<ll>> matmul(const vector<vector<ll>>& A, const vector<vector<ll>>& B){
    ll N = A.size();
    vector<vector<ll>> res(N, vector<ll>(N, 0));
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            for (int k = 0; k < N; k++){
                res[i][j] += A[i][k]*B[k][j];
                res[i][j] %= MOD;
            }
        }
    }
    return res;
}

vector<vector<ll>> matsum(const vector<vector<ll>>& A, const vector<vector<ll>>& B){
    ll N = A.size();
    vector<vector<ll>> res(N, vector<ll>(N, 0));
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            res[i][j] = (A[i][j] + B[i][j])%MOD;
        }
    }
    return res;
}

vector<vector<ll>> computeA(ll i){
    if (DP_A.find(i) != DP_A.end()){
        return DP_A[i];
    }
    vector<vector<ll>> res;
    if (i % 2 == 0){
        res = matmul(computeA(i/2), computeA(i/2));
    }
    else{
        res = matmul(matmul(computeA(i/2), computeA(i/2)), A);
    }
    DP_A[i] = res;
    return DP_A[i];
}

vector<vector<ll>> computeS(ll i){
    if (DP_S.find(i) != DP_S.end()){
        return DP_S[i];
    }
    vector<vector<ll>> res;
    if (i % 2 == 0){
        res = matmul(computeS(i/2), matsum(I, computeA(i/2)));
    }
    else{
        res = matsum(matmul(computeS(i/2), matsum(I, computeA(i/2))), computeA(i));
    }
    DP_S[i] = res;
    return DP_S[i];
}

int main(void){
    fastio;
    ll N; cin >> N;
    if (N == 1){
        cout << 1;
        return 0;
    }
    DP_A[1] = A; DP_S[0] = I; DP_S[1] = A;
    vector<vector<ll>> res = matsum(I, computeS(N-1));
    cout << res[0][0];
    return 0;
}