[11444] 피보나치 수 6

---

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

11444번: 피보나치 수 6

분할 정복 문제이다.

 

사실 행렬을 잘 몰라서 구글링을 진행함 ㅎㅎ

공식은 구글링을 참고했고 코드는 혼자 짰다!

 

참고한 공식 유도

그래서 도출된 식이 맨 아래에 있는 식이다.

행렬의 거듭제곱을 알아야 풀 수 있기 때문에 

행렬 곱셈 + 분할정복을 이용한 거듭제곱을 이용하여 풀었다.

 

이번엔 수의 범위가 굉장히 컸기 때문에 모든 자료형을 long long으로 설정해주었다.

#include <iostream>
using namespace std;

long long n;

// 행렬 계산
long long** matrix(long long** a, long long** b) {
	long long** ans = new long long* [3];
	for (int i = 0; i <= 2; i++)ans[i] = new long long[3];

	for (int i = 1; i <= 2; i++) {
		for (int j = 1; j <= 2; j++) {
			long long sum = 0;
			for (int k = 1; k <= 2; k++) {
				sum += (a[i][k] * b[k][j]);
			}
			ans[i][j] = sum % 1000000007;
		}
	}

	return ans;
}

long long** solve(long long** a, long long b) {
	if (b == 1) return a;	

	if (b % 2 == 0) {
		// even
		long long** x = solve(a, b / 2);
		long long** ans = matrix(x, x);
		return ans;
	}
	else {
		// odd
		long long** x = solve(a, (b - 1) / 2);
		long long** ans = matrix(matrix(x, x), a);
		return ans;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	long long** A = new long long* [3];
	for (int i = 0; i <= 2; i++)A[i] = new long long[3];
	A[1][1] = 1; A[1][2] = 1; A[2][1] = 1; A[2][2] = 0;

	long long** ans = solve(A, n);
	cout << ans[1][2];
	return 0;
}