22581번 - IkaNumber
더 나은 번역 있으면 알려주세요 :blobcry:
수직선의 정수 좌표점 위에 고양이의 집, 당근 1개, 토끼의 집이 이 순서대로 놓여있습니다.
$ x $에 위치해있는 오징어는, 한 번의 점프로 $ x+1 $ 또는 $ x+2 $로 이동할 수 있습니다.
당신은 오징어가 고양이의 집에서 토끼의 집까지 당근이 있는 위치에 멈추지 않고 가는 경로가 몇 개나 되는지 궁금했지만, 집의 위치나 당근의 위치를 알아낼 수가 없었습니다. 그래서, 경로의 개수로 가능한 모든 수들을 모아서 오징어 수라고 부르기로 했습니다.
다르게 말하자면, 어떤 수 $ N $이 오징어 수라는 것은, 오징어가 위 규칙을 만족하면서 갈 수 있는 경로의 개수가 정확히 $ N $개가 되는 집과 당근의 배치가 존재한다는 것을 의미합니다.
$ K $가 주어질 때, $ K $번째로 작은 오징어 수를 $ 1\,000\,000\,007 $로 나눈 나머지를 출력하세요.
첫째 줄에 정수 $ K $가 주어집니다. ($ 1 \le K \le 10^{18} $)
$ K $번째 오징어 수를 $ 1\,000\,000\,007 $로 나눈 나머지를 출력합니다.
아래는 오징어 수와, 오징어 수가 아닌 수의 예시입니다.
댓글을 작성하려면 로그인해야 합니다.
hibye1217 3년 전 2
더 나은 번역 있으면 알려주세요 :blobcry:
문제
수직선의 정수 좌표점 위에 고양이의 집, 당근 1개, 토끼의 집이 이 순서대로 놓여있습니다.
$ x $에 위치해있는 오징어는, 한 번의 점프로 $ x+1 $ 또는 $ x+2 $로 이동할 수 있습니다.
당신은 오징어가 고양이의 집에서 토끼의 집까지 당근이 있는 위치에 멈추지 않고 가는 경로가 몇 개나 되는지 궁금했지만, 집의 위치나 당근의 위치를 알아낼 수가 없었습니다. 그래서, 경로의 개수로 가능한 모든 수들을 모아서 오징어 수라고 부르기로 했습니다.
다르게 말하자면, 어떤 수 $ N $이 오징어 수라는 것은, 오징어가 위 규칙을 만족하면서 갈 수 있는 경로의 개수가 정확히 $ N $개가 되는 집과 당근의 배치가 존재한다는 것을 의미합니다.
$ K $가 주어질 때, $ K $번째로 작은 오징어 수를 $ 1\,000\,000\,007 $로 나눈 나머지를 출력하세요.
입력
첫째 줄에 정수 $ K $가 주어집니다. ($ 1 \le K \le 10^{18} $)
출력
$ K $번째 오징어 수를 $ 1\,000\,000\,007 $로 나눈 나머지를 출력합니다.
추가 설명
아래는 오징어 수와, 오징어 수가 아닌 수의 예시입니다.