BOJ 17840 피보나치 음악

난이도 : Solved.ac 기준 플래티넘 5

출처 : UNIST Programming Contest UNI-CODE 2018

 

1. 문제 설명

피보나치 수열 $f_i$ 에 대하여, $f_i \mod m$ 들을 쭉 숫자로 이어서 썼다고 하자. 예를 들어, $m = 11$ 이면 1, 1, 2, 3, 5, 8, 2 (13), 10 (21), 1 (34) 이므로 1123582101 이 된다. 이처럼 쭉 쓴 다음 전체를 문자열로 간주하고, $n$ 번째를 빠르게 찾는 문제.  

 

 

2. 풀이

$n$ 이 $10^{15}$ 정도로 매우 크고, 이러한 쿼리에 10만 번 답해야 하므로 $n$에 대해 매우 빠르게 답해야 한다. 

Pisano Period 에 의하면, 피보나치 수열의 $\mod m$ 값은 임의의 $m$ 에 대해서 어떤 주기 $p(m)$ 을 가진다. 

특히, 생각해 보면 피보나치 수열은 바로 이전 두 항에 의해서만 결정되므로, $i \neq j$ 에 대해 $f_i \mod m = f_j \mod m$ 이고 $f_{i+1} \mod m$ 이 $f_{j+1} \mod m$ 과 같다면 $j-i$ 가 주기가 된다는 사실을 알 수 있다. 결국 두 항만 맞춰 주면 되기 때문에, 비둘기집의 원리에 의해 $m^2$ 이내에 반드시 주기가 존재한다.

 

피보나치 수열 $\mod m$ 에 주기가 있다면, 각 자리를 enumerate 할 새로운 문자열에 대해서도 주기가 존재한다. 특히, $m \leq 1000$ 이므로 피보나치 수열의 각 항은 많아야 3자리씩 차지하게 되고, 따라서 길어야 $3m^2$ 이내에 우리가 원하는 문자열의 주기가 존재한다. 이 주기를 직접 찾은 다음, 모듈러를 이용해 빠르게 쿼리에 답하면 된다.

 

특히, $f_T = 1, f_{T+1} = 1$ 인 $T$ 를 찾으면 간단하게 주기를 알 수 있다.

 

 

3. 코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int ll
int fibo[1010100];
string seq;
int q, m;
int T;
int32_t main()
{
    usecppio
    cin >> q >> m;
    fibo[0] = 1;
    fibo[1] = 1;
    for (int i = 2; i<m*m; i++)
    {
        fibo[i] = (fibo[i-1] + fibo[i-2])%m;
        if (fibo[i] == 1 && fibo[i-1] == 1)
        {
            T = i-1;
            for (int j = 0; j<T; j++)
                seq += to_string(fibo[j]);
            break;
        }
    }
    if (m == 2)
        seq = "110";
    else if (m == 3)
        seq = "11202210";
    T = seq.size();
    while(q--)
    {
        int x;
        cin >> x;
        cout << seq[((x%T + T - 1)%T)] << '\n';
    }
}

구현에서 뇌절한 부분이 두 가지 정도 있었는데,

- 구현을 대충 아무렇게나 해서 $m = 2, 3$ 케이스에 대해서 제대로 답을 출력하지 못했다. 귀찮으니 직접 손으로 계산해서 넣어 주기로 했다.

- 마지막에 모듈러 하고 -1 하면 -1번에 접근할 수도 있어서 이를 안전하게 처리해야 한다.

 

string 에 + 연산자 overloading 된 부분이 언제 어떤 시간복잡도로 동작하는지 사실 잘 모르겠다. 어디선가 두 String의 길이의 합에 비례하는 시간이 든다는 걸 본거 같아서 처음에는 각 문자를 직접 push_back 했는데, 다시 내 보니 그렇게 느리지 않은 것 같다.