[Baekjoon - 22581] IkaNumber

난이도: Platinum III

 

태그

• Fibonacci Number
• Binary Search
• Exponentiation by Squaring → Matrix Exponentiation

 

풀이

1. 오징어 수를 분석해보자.

(일반성을 잃지 않고) 오징어가 출발하는 위치 (고양이의 집)을 \( 0 \)으로 고정시켜봅시다.

그리고, 당근의 위치는 \( a \), 토끼의 집의 위치는 \( b \)라고 해봅시다.

 

오징어는 당근을 건너뛰어야 하기 때문에, \( 0 \Rightarrow a-1 \rightarrow a+1 \Rightarrow b \)의 경로를 타야 합니다.

즉, 오징어가 선택할 수 있는 경로의 수는 \( 0 \Rightarrow a-1 \)의 가짓수 × \( a+1 \Rightarrow b \)의 가짓수가 됩니다.

 

\( dp_{i} \) = \( 0 \)에서 출발해서 \( i \)로 가는 경우의 수라고 해봅시다.

그럼 초항은 \( dp_{0} = dp_{1} = 1 \)이 되고, 점화식은 \( dp_{i} = dp_{i-1} + dp_{i-2} \)이 됩니다.

그러니까, 그냥 피보나치 수죠.

 

이 말은, 오징어가 선택할 수 있는 경로의 수는 두 피보나치 수의 곱으로 나타낼 수 있다는 것을 의미합니다.

게다가, \( a, b \)를 자유롭게 선택할 수 있으니, 가능한 모든 두 피보나치 수의 곱이 가능하겠죠.

 

결론적으로, 오징어 수 = 두 피보나치 수의 곱으로 나타낼 수 있는 수 가 됩니다.

 

Intermission 1. 피보나치 수의 곱을 2차원 배열에 다 적어보자.

×	1	2	3	5	8	13	21	34
1	1	2	3	5	8	13	21	34
2	-	4	6	10	16	26	42	68
3	-	-	9	15	24	39	63	102
5	-	-	-	25	40	65	105	170
8	-	-	-	-	64	104	168	272
13	-	-	-	-	-	169	273	442
21	-	-	-	-	-	-	441	714
34	-	-	-	-	-	-	-	1156

 

위 테이블을 보면서, 무언가 규칙을 찾아봅시다.

 

2. 대각선으로 인접한 두 수에 대한 분석

// 이 글에서 대각선은 오른쪽 위로 올라가는 대각선만을 의미합니다.

결론부터 말하다면, 대각선으로 인접한 두 수의 차는 항상 피보나치 수입니다.

 

1	1	2	3	5	8	13	21	34
2	-	4	6	10	16	26	42	68

 

첫 두 줄을 예시로 들면, 대각선으로 인접한 원소들의 차이가

\( [4-3 = 1, 6-5 = 1, 10-8 = 2, 16-13 = 3, 26-21 = 5, 42-34 = 8, \ldots] \)로 가는 걸 볼 수 있죠.

그리고 이는 다른 줄에 대해서도 동일합니다.

 

다만, 주의할 점이 하나 있는데, 1번 줄과 2번 줄을 비교하면 밑의 줄이 더 큰 값을 가지지만,

2번 줄과 3번 줄을 비교하면 위의 줄이 더 큰 값을 가지고,

3번 줄과 4번 줄을 비교하면 밑의 줄이 더 큰 값을 가지고,

... 의 규칙을 반복합니다.

[2]의 증명

\( F_{i} \) = \( i \)번째 피보나치 수라고 해봅시다.

엄밀히는, \( F_{0} = F_{1} = 1 \), \( F_{i} = F_{i-1} + F_{i-2} \)를 따릅니다.

 

우리가 알고 싶은 건, \( A_{y, x} = F_{y} \times F{x} \)에 대해, \( A_{y, x} \)와 \( A_{y-1, x+1} \)의 차이입니다.

즉, \( F_{y} F_{x} - F_{y-1} F_{x+1} \)의 값이죠.

 

저 값을 \( f(y, x) \)라고 해봅시다. 우리가 증명해야 할 부분은 어떤 정수 \( k \)에 대해 \( |f(y, x)| = F_{k} \)임을 보이는 것입니다.

 

우선 \( y = 1 \)부터 봅시다.

그럼, \( f(1, x) = F_{1} F_{x} - F_{0} F_{x+1} = F{x} - F_{x+1} = -F_{x-1} \)이 됩니다.

 

이제 귀납법을 사용해서, \( f(y-1, *) \)에서 \( f(y, x) \)를 봅시다. 이는 아래의 순서를 따르면 됩니다.

\[ f(y, x) = F_{y} F_{x} - F_{y-1} F_{x+1} = (F_{y-1} + F_{y-2}) F_{x} - F_{y-1} F_{x+1} = F_{y-1} (F_{x} - F_{x+1}) + F_{y-2} F_{x} = - F_{y-1}F_{x-1} + F_{y-2}F_{x} = -(F_{y-1}F_{x-1} - F_{y-2}F_{x}) = -f(y-1, x-1) \]

\( f(y-1, x-1) \)이 피보나치 수로 나타낼 수 있으니 → \( f(y, x) \) 역시 피보나치 수로 나타낼 수 있고, 증명은 끝납니다.

 

사실 여기서 하나를 더 얻어갈 수 있는데, \( f(y, x) = (-1)^{y}F_{x-y} \)입니다. 직관적으로 보이니 증명은 생략합니다.

 

3. 어느 하나의 대각선에 대한 분석

대각선에 무언가 규칙이 있다면, 더 파고들어봐야 하죠.

 

[2]의 증명에 의하면, \( A_{y, x} \)와 \( A_{y-1, x+1} \)의 차이 \( f(y, x) \)는 \( (-1)^{y}F_{x-y} \)입니다.

오른쪽 위로 올라가는 대각선은 \( x+y = k \)로 나타낼 수 있으니, \( f(y, x) \)의 값은 아래와 같이 변합니다.

// y축의 방향에 주의하세요! 위 테이블에서, y축은 아래를 향하고 있습니다!

\( [f(2, k-2), f(3, k-3), f(4, k-4), \ldots] = [F_{k-4}, -F{k-6}, F_{k-8}, \ldots] \)

// 시작점에 주의하세요! \( f(y, x) \)의 정의 상, \( A_{y-1, x+1} \)이 정의되는 위치는 \( y = 2 \)부터입니다.

 

그리고, 이를 토대로 대각선 \( y+x = k \) 위에 있는 수들의 대소 비교를 할 수 있습니다.

 

결론만 말하자면, \( B_{y} = A_{y, k-y} \)라고 하고, \( m \)을 \( B \)의 길이라고 하면

작은 수부터 순서대로 나열하면 \( [B_{1}, B_{3}, B_{5}, \ldots, B_{m-2}, B_{m}, B_{m-1}, B_{m-3}, \ldots, B_{4}, B_{2}] \)가 됩니다.

// 사실 엄밀히는, \( m \)의 홀짝성이 안 맞으면 \( m-2, m, m-1, m-3 \)의 순서가 아니겠지만,

대강 적당히 중심까지 2칸씩 점프뛰다가 / 중심에 도달하면 방향 바꿔서 2칸씩 점프뛴다는 느낌으로 보면 됩니다.

[3]에 대한 증명

대각선의 좌측 하단 점에서부터 시작해봅시다.

저희가 증명할 건, 좌측 하단 점에서부터 우측 상단으로 1칸씩 옮겨가면

새로운 수가 등장할 때마다 지금까지 본 수들의 LowerBound 또는 UpperBound가 갱신된다는 것을 보일 것입니다.

 

중심에서 시작할 때는, 자명히 Bound가 갱신됩니다.

그리고, 중심의 다음 값 역시 \( f(y, x) \)가 \( 0 \)이 아니므로, 새로운 값이 나오니 두 Bound 중 하나가 갱신되겠죠.

 

이후는 귀납법입니다.

새로운 수가 등장했고, 이 때의 수는 이전 수와 \( f(y, x) \)의 차이를 가진다고 해봅시다.

그럼, 지금까지 본 수들은 \( [\ldots, c, c+f(y+1, x-1), c+f(y+1, x-1)+f(y, x)] \)의 순서를 가지게 됩니다.

 

일반성을 잃지 않고, \( f(y, x) > 0 \)이라고 해봅시다.

// \( f(y, x) < 0 \)이라면, Upper/Lower를 뒤집어서 생각해주면 됩니다.

그럼, 지금까지 본 수들 중의 UpperBound는 \( c \)가 되고, LowerBound는 \( c+f(y+1, x-1) \)가 됩니다.

// 항상 Bound가 갱신되고, \( f \)의 부호가 계속 바뀌니, Bound의 갱신 순서가 L U L U ... 또는 U L U L ...이 될텐데,

이번에 보는 \( f(y, x) \)는 양수이므로 U가 갱신되어야 하고, 그럼 지금까지 온 값은 ... U L (U)가 되어야겠죠.

 

UpperBound가 갱신되려면, \( f(y, x) + f(y+1, x-1) > 0 \)이어야 합니다.

\( f(y, x) > 0 \)이므로, \( f(y+1, x-1) < 0 \)이니, \( |f(y, x)| > |f(y+1, x-1)| \)을 보이면 되죠.

\( |f(y, x)| = F_{x-y} \)이고, \( |f(y+1, x-1)| = F_{x-y-2} \)입니다.

자명히 \( F_{x-y} > F_{x-y-2} \)이니, 증명은 끝났습니다.

 

4. 두 인접한 대각선들에 대한 분석

맨 왼쪽에 있는 대각선부터 시작해서 수를 써보면,

1 / 2 / 3, 4 / 5, 6 / 8, 9, 10 / 13, 15, 16 / 21, 24, 25, 26 / 34, 39, 40, 42 / ...

 

뭔가 왼쪽에 있는 대각선에 있는 수들이 다 쓰여야 그 다음 대각선에 있는 수들이 등장하는 것처럼 보입니다.

그리고, 실제로도 그렇습니다.

자세한 건 아래 증명을 참고하세요.

[4]에 대한 증명

두 인접한 대각선에 대해 (왼쪽 대각선의 Upper) < (오른쪽 대각선의 Lower)를 증명한다면, 왼쪽 대각선의 수가 모두 등장해야 오른쪽 대각선의 수가 등장함을 증명할 수 있습니다.

 

대각선 \( x+y = k \)의 Lower와 Upper는, [3]에 의해 각각 \( A_{1, k-1} \)과 \( A_{2, k-2} \)가 됩니다.

저희가 증명해야 하는 건, \( x+y = k \)와 \( x+y = k+1 \)의 대각선에 대해, \( A_{2, k-2} < A_{1, k} \)가 되죠.

 

\[ A_{2, k-2} = F_{2} F_{k-2} = 2 F_{k-2} \le F_{k-2} + F_{k-1} = F_{k} = F_{1} F_{k} = A_{1, k} \]

이렇게 하면, \( A_{2, k-2} \le A_{1, k} \)까지 오게 됩니다.

하지만 등호는 \( F_{k-2} = F_{k-1} \)일 때만 성립하고, 이는 \( k = 2 \)일 때입니다.

다르게 말하자면, \( k > 2 \)일 때는 \( A_{2, k-2} < A_{1, k} \)가 증명됩니다.

 

\( k = 2 \)일 때는 무슨 문제가 발생한 걸까요?

\( x+y = 3 \)의 Upper 역할을 해줘야 할 \( A_{2, 3-2} \)가 없기 때문입니다.

그래서, 이 부분은 예외처리해주면 됩니다.

 

\( x+y = 2 \)에 있는 수는 \( 1 \)밖에 없고, \( x+y = 3 \)에 있는 수는 \( 2 \)밖에 없으니, \( k = 2 \)를 증명할 수 있습니다.

 

5. 수 자체에 대한 분석

이렇게만 하면 이제 끝난 것 같지만, 하나가 더 있습니다.

만약 위 테이블에서 어떤 수가 2번 이상 등장한다면?

 

개수를 세다가 특정 수를 여러 번 세게 된다면 무슨 일이 발생할 수도 있으니, 확인해봅시다.

 

[4]에 의해, 두 다른 대각선에서 같은 수가 나올 걱정은 하지 않아도 됩니다.

또한, [5]에 의해, 시작점을 기준으로 증가하는 부분 수열과 감소하는 부분 수열로 나눠서 보면

(증가, 감소)에서 겹치는 수는 자명히 없고, (증가, 증가)에서도 자명히 없습니다.

// (증가, 감소): 시작점이 동일해서 증가의 Lower = 감소의 Upper가 됩니다. 그런데 저게 진짜 =이 되는 때는 둘의 공통 원소인 시작점 뿐이기 때문에 예외처리하면, 증가의 Lower > 감소의 Upper가 되죠.

// (증가, 증가): strictly increasing하기 때문에, 동일한 원소가 있을 수 없습니다.

// (감소, 감소): strictly decreasing이므로, 역시 동일한 원소가 없습니다.

 

그러니, 개수를 셀 때 같은 수를 여러 번 세는 걱정은 안 해도 됩니다.

 

6. 구현 디테일

\( K \)번째 수를 찾는 건 아래와 같은 방식으로 진행됩니다.

\( K \)번째 수가 속한 \( x+y = k \) 대각선 찾기. [4]에 의해, 이진 탐색을 사용할 수 있다.

→ \( x+y = k \) 대각선에서 \( K \)번째 수 찾기. [3]을 사용해서 \( O(1) \)에 찾아줄 수 있다.

→ \( A_{y, x} = F_{y} \times F_{x} \) 찾기. \( F_{N} \)을 \( O(\log N) \) 시간에 찾아주면 된다.

 

7. 코드

mod = 1_000_000_007
 
def f(x):
    x -= 1
    a, b = x//2, (x+1)//2
    return a*(a+1)//2 + b*(b+1)//2
 
def mmul(a, b):
    c = [ [0, 0], [0, 0] ]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                c[i][j] += a[i][k]*b[k][j]
                c[i][j] %= mod
    return c
 
 
def fib(n):
    mul, res = [ [1, 1], [1, 0] ], [ [1, 0], [0, 1] ]
    while n:
        if n&1: res = mmul(res, mul)
        mul = mmul(mul, mul); n >>= 1
        #print(res, mul, n)
    return res[1][0] + res[1][1]
 
k = int( input() )
st, ed, idx = 1, 10**18, 10**18
while st <= ed:
    #print(st, ed)
    mid = (st+ed) // 2
    if k <= f(mid): ed, idx = mid-1, mid
    else: st = mid+1
k -= f(idx-1)
c = idx // 2
if c%2 == 0:
    if k <= c//2: a = 2*k-1
    else:
        k -= c//2; a = c-2*k+2
else:
    if k <= (c+1)//2: a = 2*k-1
    else:
        k -= (c+1)//2; a = c-2*k+1
b = idx-a
#print(a, b, idx)
print(fib(a)*fib(b) % mod)