BOJ 11444 - 피보나치 수 6 (행렬곱, 점화식 이용)

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

 

MOD가 10의 거듭제곱꼴이 아니므로 피사노 주기를 사용할수 없다. 따라서 행렬곱을 이용해야 한다.

 

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

설명은 이곳 참고

 

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> matrix;
const ll MOD = 1000000007LL;

matrix operator * (const matrix& a, const matrix& b) {
	int n = a.size();
	matrix c(n, vector<ll>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				c[i][j] += a[i][k] * b[k][j];
			}
			c[i][j] %= MOD;
		}
	}
	return c;
}

int main() {
	ll n; cin >> n;
	if (n <= 1) {
		cout << n << '\n';
		return 0;
	}

	matrix ans = { {1,0}, {0,1} };
	matrix a = { {1,1}, {1,0} };

	while (n > 0) {
		if (n % 2 == 1) ans = ans * a;
		a = a * a;
		n /= 2;
	}

	cout << ans[0][1] << '\n';
}

코드 복붙. main 안쪽은 재귀를 이용한 분할정복을 간략화 한 것.

 

 

#include <iostream>
#include <map>
using namespace std;
typedef long long ll;
map<ll, ll> dp;
const ll MOD = 1000000007LL;

ll fibo(ll k) {
	if (k <= 1) return k;
	if (k == 2) return 1;
	if (dp.count(k) > 0) return dp[k];

	ll& ret = dp[k];
	if (k % 2 == 1) {
		ll m = (k + 1) / 2;
		ll t1 = fibo(m);
		ll t2 = fibo(m - 1);
		ret = t1 * t1 + t2 * t2;
		ret %= MOD;
	}
	else {
		ll m = k / 2;
		ll t1 = fibo(m - 1);
		ll t2 = fibo(m);
		ret = (2LL * t1 + t2) * t2;
		ret %= MOD;
	}

	return ret;
}

int main() {
	ll n; cin >> n;
	cout << fibo(n) << '\n';
}

피보나치 홀수일때, 짝수일때를 나눠서 푼 코드. O(logn)에 수행됨.

map을 이용해서 dp를 짤 수 있다. (count로 메모가 됐는지 확인, 인덱스로 접근 가능)