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[100007],Fl[107][100007],Fr[107][100007]; int ls[107],ks=0; long long f[107]; int main(){ Fl[0][0]=Fr[0][0]='0'; Fl[1][0]=Fr[1][0]='1'; ls[0]=ls[1]=1; for(int i=2;i<=100;++i){ ls[i]=ls[i-1]+ls[i-2]; if(ls[i]>100000)ls[i]=100000; for(int j=0;j<ls[i];++j){ Fl[i][j]=(j<ls[i-1]?Fl[i-1][j]:Fl[i-2][j-ls[i-1]]); Fr[i][j]=(j<ls[i-2]?Fr[i-2][j]:Fr[i-1][j-ls[i-2]]); } } while(scanf("%d",&n)==1){ scanf("%s",s); int len=strlen(s); f[0]=f[1]=0; if(len==1)f[s[0]-'0']=1; for(int i=2;i<=n;++i){ f[i]=f[i-1]+f[i-2]; for(int j=1;j<len;++j)if(j<=ls[i-1]&&len-j<=ls[i-2]){ for(int k=0;k<len;++k)if(s[k]!=(k<j?Fr[i-1][j-1-k]:Fl[i-2][k-j]))goto o; ++f[i]; o:; } } printf("Case %d: %lld ",++ks,f[n]); } return 0; }