8406번 - 피보나치 단어 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 80 | 5 | 4 | 28.571% |
문제
피보나치 단어의 수열은 다음과 같이 정의한다.
Fib0 = b, Fib1 = a, Fibn = Fibn-1Fibn-2 (n ≥ 2)
Fibn은 Fibn-1과 Fibn-2를 이어 붙인 것이다.
피보나치 단어 수열의 첫 부분은 b,a,ab,aba,abaab,abaababa,abaababaabaab,... 이다.
단어 u가 단어 v의 부분 단어가 되려면, 임의의 단어 x와 y에 대해서 v = xuy로 쓸 수 있어야 한다. (x와 y는 빈 단어일 수도 있다)
a와 b로만 이루어진 단어 α와 피보나치 단어 Fibm을 나타내는 m이 주어진다. 이때, Fibm에 α가 부분 단어로 몇 번 등장하는지 구하고, Fibm의 부분 단어 중에서 α가 적어도 등장하는 횟수만큼 등장하는 비어있지 않은 부분 단어의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 m (0 ≤ m ≤ 1,000,000,000)이 주어진다. 둘째 줄에는 단어 α가 주어진다. α는 a와 b로만 이루어져 있으며, 길이는 1,000,000을 넘지 않는다.
출력
첫째 줄에 두 숫자를 출력한다. 첫 번째 숫자는 Fibm에 α가 부분 단어로 총 몇 번 등장하는지를 나타내는 숫자이다. 두 번째 단어는 Fibm의 모든 부분 단어 중에서, 적어도 α가 등장하는 만큼 등장하는 비어있지 않은 부분 단어의 개수를 출력한다.
두 숫자는 매우 클 수 있기 때문에 20062006으로 나눈 나머지를 출력한다.
입력으로 주어지는 α는 항상 주어진 피보나치 단어의 부분 단어이다.
예제 입력 1
5 aba
예제 출력 1
3 5
힌트
Fib5에서 적어도 aba가 등장하는 만큼 등장하는 비어있지 않은 부분 단어는 a, b, ab, ba, aba이다.
출처
Contest > Algorithmic Engagements > PA 2006 6-1번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호