Problems
The Fibonacci word sequence of bit strings is defined as:
F(N) = 0, if N = 0
F(N) = 1, if N = 1
F(N) = F(N - 1) + F(N - 2), if N ≥ 2
Here + denotes concatenation of strings. The first few elements are:
<Example>
Given a bit pattern p and a number n, how often does p occur in F(n)?
Input
The first line of each test case contains the integer n (0 ≤ n ≤ 100). The second line contains the bit pattern p. The pattern p is nonempty and has a length of at most 100 000 characters.
Output
For each test case, display its case number followed by the number of occurrences of the bit pattern p in F(n). Occurrences may overlap. The number of occurrences will be less than 263.
Example
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
Source
ACM ICPC 2012 World Final D
You must sign in to write code.