题目描述

斐波那契01字符串的定义如下 F(n) = { 0 if n = 0 1 if n = 1 F(n-1)+F(n-2) if n >= 2 } 这里+的定义是字符串的连接。F(n)的前几个元素如下： F(0)=0 F(1)=1 F(2)=10 F(3)=101 F(4)=10110 F(5)=10110101 F(6)=1011010110110 F(7)=101101011011010110101 F(8)=1011010110110101101011011010110110 F(9)=1011010110110101101011011010110110101101011011010110101 给定一个模式串p和一个数n，p在F(n)中出现了多少次？

输入格式

每个测试点包含多组测试数据。 每组测试数据的第一行包含一个正整数n。第二行包含模式串p。

输出格式

对于每个测试数据，输出测试数据编号和p在F(n)出现的次数。出现的位置可能会重叠。

10
7
10
6
01
6
101
96
10110101101101
样例输出
Case 1: 5
Case 2: 8
Case 3: 4
Case 4: 4
Case 5: 7540113804746346428

output1

提示

数据规模和约定 0<=n<=100 p非空且包含最多100000个字符 p出现的次数严格小于2^63。 关于多组测试数据 Case Limit <= 30 存在20组数据满足n<=20,len(p)<=100 另有20%的数据满足len(p)<=100（总共有百分之多少呢？）

题目来源

没有写明来源