백준 11440 c++ "피보나치 수의 제곱의 합" -PlusUltraCode-

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

[필자 사고]

처음으로 만난 행렬을 이용하여 수식을 계산하는 문제를 만났다. 

익숙하지가 않아서 개념을 잘 숙지 하고 문제를 봐야겠다.

[코드 해설]

 

• 행렬을 이용한 피보나치 수열 계산
  이 코드는 행렬 거듭제곱을 사용하여 피보나치 수열을 효율적으로 계산합니다.
  • 피보나치 수열은 다음과 같은 행렬식을 통해 계산될 수 있습니다: Base Matrix=[1110]\text{Base Matrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}Base Matrix=[11​10​] 이 행렬을 제곱하여 원하는 인덱스의 피보나치 수를 빠르게 구할 수 있습니다.
• multiplyMatrices 함수
  이 함수는 두 행렬의 곱셈을 수행합니다.
  • 두 2x2 행렬을 곱하며, 모든 값은 모듈러 연산 (MOD=109+7MOD = 10^9 + 7MOD=109+7)을 적용합니다.
  • 3중 for문을 사용하여 행렬의 각 원소를 계산합니다.
• calculateFibonacci 함수
  • 피보나치 수열 계산의 핵심으로, 거듭 제곱법을 사용하여 시간 복잡도를 줄입니다.
  • 초기 행렬을 단위 행렬(Identity Matrix)로 설정합니다.
  • 주어진 지수 nnn에 대해:
    • nnn이 홀수일 경우, 단위 행렬에 현재의 행렬을 곱합니다.
    • 행렬을 제곱하여 다음 단계를 준비합니다.
  • 최종적으로 단위 행렬의 특정 원소에서 결과 피보나치 값을 반환합니다.
• main 함수
  • 사용자로부터 피보나치 인덱스(nnn)를 입력받습니다.
  • nnn번째 피보나치 수와 n+1n+1n+1번째 피보나치 수를 각각 계산합니다.
  • 이 두 값을 곱한 뒤, 모듈러 연산을 적용하여 결과를 출력합니다.

 

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;
using Matrix = vector<vector<ll>>;

#define MATRIX_SIZE 2
#define MOD 1000000007

ll fibonacciIndex;

Matrix multiplyMatrices(Matrix& a, Matrix& b) {
	Matrix result(MATRIX_SIZE, vector<ll>(MATRIX_SIZE, 0));
	for (int i = 0; i < MATRIX_SIZE; i++) {
		for (int j = 0; j < MATRIX_SIZE; j++) {
			for (int k = 0; k < MATRIX_SIZE; k++) {
				result[i][j] = (result[i][j] + a[i][k] + b[k][j]) % MOD;

			}
		}
	}
	return result;
}

ll calculaterFibonacci(ll n) {
	Matrix baseMatrix = { {1,1,},{1,0} };
	Matrix identityMatrix = { {1,0},{0,1} };

	while (n > 0) {
		if (n % 2 == 1) {
			identityMatrix = multiplyMatrices(identityMatrix, baseMatrix);
		}
		baseMatrix = multiplyMatrices(baseMatrix, baseMatrix);
		n /= 2;
	}

	return identityMatrix[1][0];
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> fibonacciIndex;

	ll nthFibonacci = calculaterFibonacci(fibonacciIndex);
	ll nextFibonacci = calculaterFibonacci(fibonacciIndex + 1);
	ll result = (nthFibonacci * nextFibonacci) % MOD;

	cout << result << '\n';

}