BOJ 2749 - 피보나치 3 (MOD=10^k꼴일 때 주기 이용)

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

 

피보나치를 MOD로 나눈 나머지는 항상 주기를 갖는다. (피사노 주기라고 함)

 

그중 특히

MOD = 10^k  (k>2) 인 경우 PRD = 15*10^(k-1)이다.

 

fibo(n)의 값은 fibo(n%PRD)의 값과 같아진다.

 

피보나치를 dp를 이용하여 풀게되면 O(n)에 풀 수 있으므로 이 방법을 이용하면 O(MOD)라고 볼 수 있겠다.

 

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MOD = 1e6;
const int PRD = 15e5;

ll dp[PRD];

ll fibo(int k) {
	if (k <= 1) return k;

	ll& ret = dp[k];
	if (ret != -1) return ret;

	return ret = (fibo(k - 1) + fibo(k - 2))%MOD;
}

int main() {
	ll n; cin >> n;
	fill(dp, dp + PRD, -1);
	cout << fibo(n%PRD) << '\n';
}

 

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

참고했습니다