[WF2012]Fibonacci Words
时间限制：1s 空间限制：256MB
题目描述
斐波那契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)出现的次数。出现的位置可能会重叠。
样例输入
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
样例输出
提示
数据规模和约定
0<=n<=100
p非空且包含最多100000个字符
p出现的次数严格小于2^63。
关于多组测试数据
Case Limit <= 30
存在20组数据满足n<=20,len(p)<=100
另有20%的数据满足len(p)<=100（总共有百分之多少呢？）
题目来源
没有写明来源