레이팅 미적용설명
비트 문자열의 피보나치 단어 수열은 다음과 같이 정의된다. \(F\)(\(n\)) = if \(n = 0\) if \(n = 1\) \(F\)(\(n - 1\)) + \(F\)(\(n - 2\)) if \(n \ge 2\) 여기서(He\(re + de\)notes) +는 문자열의 이어 붙이기를 뜻한다. 처음 몇 원소는 다음과 같다. \(n\) \(F\)(\(n\)) 101 10110 10110101 1011010110110 101101011011010110101 1011010110110101101011011010110110 1011010110110101101011011010110110101101011011010110101 비트 패턴 \(p\)와 수 \(n\)이 주어질 때, \(p\)는 \(F\)(\(n\))에 몇 번 나타나는가?
제약
입력 형식
각 테스트 케이스의 첫 줄에는 정수 \(n\) (\(0 \le n \le 100\))이 주어진다. 둘째 줄에는 비트 패턴 \(p\)가 주어진다. 패턴 \(p\)는 비어 있지 않으며 길이는 최대 100 000이다.
출력 형식
각 테스트 케이스마다 케이스 번호와 함께 비트 패턴 \(p\)가 \(F\)(\(n\))에 나타나는 횟수를 출력한다. 나타나는 위치는 겹칠 수 있다. 나타나는 횟수는 \(2^{63}\)보다 작다.
예제 1
입력
6
10
7
10
6
01
6
101
96
10110101101101
출력
Case 1: 5
Case 2: 8
Case 3: 4
Case 4: 4
Case 5: 7540113804746346428
문제 정보