[백준 11444] 피보나치 수6

문제출처: https://www.acmicpc.net/problem/11444

행렬의 곱셈을 이용하여 분할정복 기법으로 푸는 문제입니다.

아래 링크에서 행렬곱셈을 이용한 접근방법에대해 공부하시고 풀 것을추천드립니다.

https://jow1025.tistory.com/101

풀이

입력값이 0일 때 0이출력되게끔만 해주면되고, 범위가 크기때문에 행렬을 담는변수, 입력 변수를 long long 형으로 선언해야합니다.

풀이는 행렬곱셈만할줄 알면되므로 생략하겠습니다.

코드

#include<iostream>
struct M
{
	long long data[2][2];
};
using namespace std;
long long fibo(long long x);
M divide(M a, long long x);
M multiply(M a, M b);
int main()
{
	long long n;
	cin >> n;
	if (n == 0) { cout << 0 << endl; return 0; }
	cout << fibo(n) << endl;
}
long long fibo(long long x)
{

	M a;
	a.data[0][0] = 1; a.data[0][1] = 1;
	a.data[1][0] = 1; a.data[1][1] = 0;
	a = divide(a, x);
	return a.data[0][1];
}
M divide(M a, long long  x)
{
	if (x > 1)
	{
		a = divide(a, x / 2);
		a = multiply(a, a);
		if (x % 2 == 1)
		{
			M b;
			b.data[0][0] = 1; b.data[0][1] = 1;
			b.data[1][0] = 1; b.data[1][1] = 0;
			a = multiply(a, b);
		}
	}
	return a;
}
M multiply(M a, M b)
{
	M c;
	c.data[0][0] = (a.data[0][0] * b.data[0][0] + a.data[0][1] * b.data[1][0])%1000000007;
	c.data[0][1] = (a.data[0][0] * b.data[0][1] + a.data[0][1] * b.data[1][1]) % 1000000007;
	c.data[1][0] = (a.data[1][0] * b.data[0][0] + a.data[1][1] * b.data[1][0]) % 1000000007;
	c.data[1][1] = (a.data[1][0] * b.data[0][1] + a.data[1][1] * b.data[1][1]) % 1000000007;
	return c;

}

결과