[BOJ] 11444 - 피보나치 수 6 (C++)

문제

피보나치 수 6

코드

#include<iostream>
#include<vector>

using namespace std;

const long long mod = 1000000007;
long long n;

vector< vector<long long> > multiple (vector< vector<long long> >& a, vector< vector<long long> >& b){
	vector< vector<long long> > c(2, vector<long long>(2));

	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++){
			for (int k = 0; k < 2; k++)
				c[i][j] += a[i][k] * b[k][j];

			c[i][j] %= mod;
		}
	return c;	
}

int main(){
	cin >> n;

	vector< vector<long long> > ans = {{1,0}, {0,1}};
	vector< vector<long long> > a = {{1,1}, {1,0}};

	while (n > 0){
		if (n % 2 == 1) ans = multiple(ans, a);
		a = multiple(a, a);
		n /= 2;
	}
	
	cout << ans[0][1] << '\n';
}

접근

이 문제는 피보나치 수 3와는 다르게 피사노 주기를 이용할 수 없다. 이유는 한 번의 주기까지 구할수가 없기 때문이다. 정수론을 도입해서 구한다면 주기가 2,000,000,016이라고 한다. 이 크기의 배열을 선언할 수도 없고, 반복문으로 돌기에 시간제한도 걸리게 된다고 한다.

따라서 이 문제는 피보나치 수의 점화식을 행렬로 나타내어 풀어야 한다. 점화식을 정리하면 아래와 같고 행렬 제곱을 계산하여 결과를 구할 수 있다.

참고
https://www.acmicpc.net/blog/view/28