[WF2012]Fibonacci Words

内存限制：256 MiB 时间限制：1 Sec

斐波那契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（总共有百分之多少呢？）

BZPRO Powered by Remmina.
Github Repository

#3978. [WF2012]Fibonacci Words