R00378
도미노 타일링
플래티넘 V레이팅
의견: 0
설명
\(2 \times N\) 크기의 직사각형 격자를 \(1 \times 2\) 또는 \(2 \times 1\) 크기의 도미노로 빈틈없이, 겹치지 않게 덮는 방법의 수를 구하여라. 답을 \(1{,}000{,}000{,}007\) 로 나눈 나머지를 출력한다.
이 수는 피보나치 수를 따른다: \(f(0) = 1\), \(f(1) = 1\), \(f(n) = f(n-1) + f(n-2)\). (\(N=0\) 이면 빈 격자를 덮는 방법은 1가지로 본다.)
\(N\) 이 최대 \(10^{18}\) 이므로 행렬 빠른 거듭제곱으로 \(O(\log N)\) 에 계산해야 한다.
제약
\(0 \le N \le 10^{18}\)
입력 형식
첫째 줄에 정수 \(N\) 이 주어진다.
출력 형식
\(2 \times N\) 격자를 도미노로 덮는 방법의 수를 \(1{,}000{,}000{,}007\) 로 나눈 나머지로 출력한다.
예제 1
입력
4
출력
5설명
\(2\times4\) 격자를 도미노로 덮는 방법은 5가지이다(\(f(4)=5\)).
예제 2
입력
0
출력
1설명
\(N=0\) 인 빈 격자를 덮는 방법은 1가지로 정의한다.
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
도미노 타일링
개요
Log in to rate problems.
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
도미노 타일링
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기