D. Fibonacci Words
레이팅 미적용의견: 0
The Fibonacci word sequence of bit strings is defined as: \(F\)(\(n\)) = if \(n = 0\) if \(n = 1\) \(F\)(\(n - 1\)) + \(F\)(\(n - 2\)) if \(n \ge 2\) He\(re + de\)notes concatenation of strings. The first few elements are: \(n\) \(F\)(\(n\)) 101 10110 10110101 1011010110110 101101011011010110101 1011010110110101101011011010110110 1011010110110101101011011010110110101101011011010110101 Given a bit pattern \(p\) and a number \(n\), how often does \(p\) occur in \(F\)(\(n\))?
The first line of each test case contains the integer \(n\) (\(0 \le n \le 100\)). The second line contains the bit pattern \(p\). The pattern \(p\) is nonempty and has a length of at most 100 000 characters.
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 \(2^{63}\).
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
평가 및 의견
D. Fibonacci Words
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
D. Fibonacci Words