피보나치 수열 정리 (백준 2749 피보나치 수 3, 11444 피보나치 수 6)
1. 피보나치 수열이란?
피보나치 수열은 0번째, 1번째 항이 0, 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.
피보나치 수열의 점화식을 세워 보자면 $ F_{n} = F_{n-1} + F_{n-2} (n>=2) $ 이다.
위의 식처럼 점화식이 무척 간단하기 때문에 N의 수가 작을 경우에는 동적 계획법을 통해 피보나치 수를 구할 수 있다.
2748번: 피보나치 수 2
문제 피보나치 수는 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번째 피보나치 수를
www.acmicpc.net
소스코드
ll fib[91];
int main()
{
SYNC;
cin >> n;
fib[0] = 0;
fib[1] = 1;
fu(i, 2, n + 1) {
fib[i] = fib[i - 1] + fib[i - 2];
}
cout << fib[n];
return 0;
}
하지만 동적계획법으로 구하는 방식은 $O(N)$이므로 N이 커지게 되면 다른 방식을 통해 구해야한다.
2749번 피보나치 수 3 에서는 주어지는 N의 크기가 $10^{18}$이다. 그렇기에 $O(N)$으로는 시간 초과가 나게 된다. 그래도, N의 크기가 크다보니 정답을 표현할 수 있도록 $10^6$으로 나눈 나머지를 출력하면 된다.
2749번: 피보나치 수 3
첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
피보나치 수를 K로 나눈 나머지는 항상 주기를 갖는다. 그 주기를 피사노 주기(Pisano Period)라고 부른다.
이 피사노 주기는 M(나누는 값) = $10^k$ 일 때, $k>2$라면, 주기는 항상 $15 \times 10^{k-1}$이다.
이 주기 공식을 몰라도 피보나치 수의 0번째, 1번째 수가 0 1 임을 이용하여 주기를 구할 수 있다.
소스코드
vi fib;
int main()
{
SYNC;
ll n;
cin >> n;
ll pre1 = 0;
ll pre2 = 1;
ll now = 1;
fib.push_back(0);
fib.push_back(1);
m = 1;
fu(i, 2, n + 1) {
now = (pre1 + pre2) % 1000000;
pre1 = pre2;
pre2 = now;
fib.push_back(now);
if (pre1 == 0 && pre2 == 1) {
m = i - 1;
break;
}
}
if (m == 1)
cout << fib[n];
else
cout << fib[n % m];
return 0;
}
11444번 피보나치 수 6 문제는 피보나치 수 3과 같이 N의 제한은 $10^{18}$이지만 1,000,000,007로 나눈 나머지를 구해야한다. 따라서 피사노 주기를 사용하더라도 TLE가 나게된다. 그래서 이번에는 다른 방법인 행렬을 이용해야 한다.
11444번: 피보나치 수 6
첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
피보나치 수는 $ F_{n} = F_{n-1} + F_{n-2} (n>=2) $ 이다. 따라서 이 성질을 이용하여 행렬로 표현할 수 있다.
${\begin{pmatrix} F_{n+2} \\ F_{n+1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\1 & 0 \end{pmatrix} \begin{pmatrix} F_{n+1} \\ F_{n} \end{pmatrix}}$
이 식을 정리하면
${ \begin{pmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n }$
결국 $F_n$을 행렬의 거듭제곱의 형태로 표현이 가능하므로 행렬 제곱을 구하면 된다.
어떤 수의 거듭 제곱은 분할 정복이나 비트를 이용해 $O(\lg{k})$ 시간으로 구할 수 있다. - 1629번 곱셈
소스코드
ll A[N][N];
ll B[N][N];
ll tmp[N][N];
ll ans[N][N];
void calc(ll res[N][N], ll mat1[N][N], ll mat2[N][N]) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
ll sum = 0;
for (int k = 0; k < n; k++) {
sum += mat1[i][k] * mat2[k][j] % MOD;
}
res[i][j] = sum % MOD;
}
}
}
void solve(ll b) {
for (int i = 0; i < n; i++) {
ans[i][i] = 1;
}
while (b) {
if (b & 1) {
memcpy(tmp, ans, sizeof tmp);
calc(ans, tmp, A);
}
calc(B, A, A);
memcpy(A, B, sizeof A);
b >>= 1;
}
}
int main()
{
SYNC;
ll m;
n = 2;
A[0][0] = 1;
A[0][1] = 1;
A[1][0] = 1;
cin >> m;
solve(m-1);
cout << ans[0][0];
return 0;
}