[Baekjoon - 22581] IkaNumber

난이도: Platinum III

 

태그

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

 

풀이

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

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

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

 

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

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

 

$d{p}_i$ = $0$에서 출발해서 $i$로 가는 경우의 수라고 해봅시다.

그럼 초항은 $d{p}_0=d{p}_1=1$이 되고, 점화식은 $d{p}_i=d{p}_{i-1}+d{p}_{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,\dots ]$로 가는 걸 볼 수 있죠.

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

 

다만, 주의할 점이 하나 있는데, 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 Fx$에 대해, $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}=Fx-F_{x+1}=-F_{x-1}$이 됩니다.

 

이제 귀납법을 사용해서, $f(y-1,\ast )$에서 $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),\dots ]=[F_{k-4},-Fk-6,F_{k-8},\dots ]$

// 시작점에 주의하세요! $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,\dots ,B_{m-2},B_m,B_{m-1},B_{m-3},\dots ,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)$의 차이를 가진다고 해봅시다.

그럼, 지금까지 본 수들은 $[\dots ,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}=2F_{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)