백준 2749, 피보나치 수 3

문제

 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. ( 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 ... ) n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력한다.

예제 입력 1 

1000

예제 출력 1 

228875

 일단 다음의 수학적 사실을 알아야 한다. 피보나치 수열에 대해서 다음의 행렬식이 성립한다. 

결론적으로 이 식을 정리하게 되면 [fn+1, fn]에 대해서 [1 1 1 0]을 n 번 거듭 제곱한 것을 [f1 f0]에 곱한 것과 같다는 것을 알 수 있다. 행렬의 거듭제곱에 대해서는 다른 글에서 다루었으니 그 글에서 참고하자. 

https://messy-developing-diary.tistory.com/15?category=1109673

백준 10830, 행렬 제곱

한 가지 다른 점은 행렬 곱셈을 하는 과정에서 어처피 해주어야 할 모듈러 연산을 미리 해주었다는 것이다. 아래의 코드는 내가 짠 코드이다.

#include <iostream>
#include <vector>

#define MOD 1000000

using namespace std;

vector<unsigned long long> matrix = 
	{1, 1, 
	1, 0};

vector<unsigned long long> operator*(vector<unsigned long long> m1, vector<unsigned long long> m2) {
	vector<unsigned long long> result(4);

	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < 2; k++) {
				result[2 * i + j] += (m1[2*i +k] * m2[2 * k + j])%MOD;
			}
		}
	}

	for (int i = 0; i < 4; i++) {
		result[i] = result[i] % MOD;
	}

	return result;
}

vector<unsigned long long> pow(unsigned long long n) {
	if (n == 1) {
		return matrix;
	}
	else if (n%2 == 0) {
		vector<unsigned long long> half = pow(n/2);
		return half * half;
	}
	else {
		vector<unsigned long long> half = pow(n / 2);
		return half * half * matrix;
	}
}

int main() {
	int input;
	std::cin >> input;

	vector<unsigned long long> result = pow(input);

	std::cout << result[2];

	return 0;
}

 결과적으로 이 코드는 백준 코드에서 틀렸다는 판정을 받았다. 예제의 답을 넣었을 때도 맞았고, 다른 입력도 해보았는 데, 예상되는 결과값들이 나와서 왜 틀렸는지는 모르겠다. 다른 사람들은 어떻게 풀었나 보았는데, 나처럼 접근하였거나, 피사노 주기라고 피보나치 수열에 모듈러에 따라서 고유의 주기가 존재한다는 것을 이용하여 간단하게 풀었더라. 이것으로 글을 마친다.