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

해결법

피보나치 수열의 값을 구하는 방법

피보나치 수열이란, 다음 항이 이전 두 개의 항의 합으로 표현되는 수열이다.
피보나치 수열의 N번째 항을 구하는 다양한 방법들을 알아보자

재귀함수

시간복잡도 : $O(2^N)$

f(int n){
	if(n<=2) return 1;
    else return f(n-1)+f(n-2);
}

이 때 피보나치 수열을 구하기 위해 호출해야하는 함수의 횟수는, n이 증가할수록 기하급수적으로 증가하게 된다.

동적계획법

시간복잡도 : $O(N)$
[BOJ]피보나치 수 2

void fibo(int n)
{
    fib[0] = 0;
    fib[1] = 1;

    for (int i = 2; i <= n; i++)
    {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
}

한번 구해놓으면 N보다 작은 피보나치 수열의 값을 구할 때 $O(1)$만에 빠르게 구해낼 수 있다.

행렬(Matrix)을 사용하는 방법

시간복잡도 : $O(\log N)$
피보나치 수열의 일반항은 $f(n) = f(n-1) + f(n-2)$ 이므로,
이를 행렬식으로 나타내면 $\begin{pmatrix}f(n)\\f(n-1)\end{pmatrix}=\begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix}f(n-1)\\f(n-2)\end{pmatrix}$ 이다.
위 식을 정리해보면 다음과 같다.

$\begin{pmatrix}f(n)\\f(n-1)\end{pmatrix}=\begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix}f(n-1)\\f(n-2)\end{pmatrix}=\begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix}f(n-2)\\f(n-3)\end{pmatrix}=\cdots$

$={\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n-2}\begin{pmatrix}f(2)\\f(1)\end{pmatrix}$

즉, 시간복잡도 $O(\log N)$만에 피보나치 수열의 값을 구할 수 있게 됐다.

BOJ 2749에서는 ...

n이 굉장하다.. 1e8(1초)는 가볍게 넘겨버리겠다
그래서 $O(\log N)$의 시간복잡도를 가지는 행렬을 이용하여 풀고자 한다.
$\begin{pmatrix}f(n)\\f(n-1)\end{pmatrix}={\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n-2}\begin{pmatrix}f(2)\\f(1)\end{pmatrix}$ 에서 $n-2$회의 거듭제곱 연산을 해야하는데 ...

거듭제곱 연산을 빠르게 할 수는 없을까?

거듭제곱을 빠르게 연산하기

숫자를 예로 들어보자.
$7^{21}$을 계산한다고 가정했을 때 $7^{21} = 7\times7\times\cdots\times7$ 처럼 7을 21번 곱할것인가?
$7^{21}$을 다시 들여다보자. $7^{21} = 7^{16}\times7^{4}\times7$ 처럼 나타낼 수 있다.
지수인 $21$을 이진법으로 나타내면 $21_{(10)}=10101_{(2)}$ 이므로, 이진법으로 나타냈을 때 1인 자리만 곱해주면 되는것이다.
👉 계산이 훨씬 줄어들었다!!

소스코드

#include <bits/stdc++.h>
#define ll long long
using namespace std;

typedef vector<vector<ll> > matrix;
const ll MOD = 1e6;

ll N;
matrix op = {{1,1},{1,0}};

//행렬 곱
matrix dot(matrix &a, matrix &b){
  ll size = a.size();
  matrix ret(size, vector<ll>(size));
  for(ll i = 0; i < size; i++) {
		for(ll j = 0; j < size; j++) {
      		ll sum = 0;	
			for(ll k = 0; k < size; k++)
				sum += a[i][k]*b[k][j];
			ret[i][j] = (ret[i][j] + sum) % MOD;
		}
	}
	return ret;
}

//행렬 거듭제곱
matrix power (matrix a, ll n){
  ll size = a.size();
  matrix ret(size, vector<ll>(size));
  //단위행렬로 초기화 ( EA = AE = A , A는 정사각행렬 E는 단위행렬)
  for(ll i = 0; i<size; i++){
    ret[i][i] = 1;
  }
  //지수를 이진법으로 바꾸어 거듭제곱을 빠르게 연산
  while(n>0){
    if(n%2==1){
      ret = dot(ret,a);
    }
    n = n>>1;
    a = dot(a,a);
  }
  return ret;
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);

  cin >> N;
  matrix ans = (power(op,N-1));
  cout << (ans[1][0]+ans[1][1]) % MOD;
}

제출결과