Description
斐波那契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)中出现了多少次？
Input
每个测试点包含多组测试数据。
每组测试数据的第一行包含一个正整数n。第二行包含模式串p。
Output
对于每个测试数据，输出测试数据编号和p在F(n)出现的次数。出现的位置可能会重叠。
递归求出询问串在F(i)中的出现次数
f[i]=f[i-1]+f[i-2]+(F(i-1)与F(i-2)的交界上的出现次数)
#include<bits/stdc++.h>
int n;
char s[],Fl[][],Fr[][];
int ls[],ks=;
long long f[];
int main(){
Fl[][]=Fr[][]='';
Fl[][]=Fr[][]='';
ls[]=ls[]=;
for(int i=;i<=;++i){
ls[i]=ls[i-]+ls[i-];
if(ls[i]>)ls[i]=;
for(int j=;j<ls[i];++j){
Fl[i][j]=(j<ls[i-]?Fl[i-][j]:Fl[i-][j-ls[i-]]);
Fr[i][j]=(j<ls[i-]?Fr[i-][j]:Fr[i-][j-ls[i-]]);
}
}
while(scanf("%d",&n)==){
scanf("%s",s);
int len=strlen(s);
f[]=f[]=;
if(len==)f[s[]-'']=;
for(int i=;i<=n;++i){
f[i]=f[i-]+f[i-];
for(int j=;j<len;++j)if(j<=ls[i-]&&len-j<=ls[i-]){
for(int k=;k<len;++k)if(s[k]!=(k<j?Fr[i-][j--k]:Fl[i-][k-j]))goto o;
++f[i];
o:;
}
}
printf("Case %d: %lld\n",++ks,f[n]);
}
return ;
}