Description
定义$F(x)$为$F(x−1)$与$F(x−2)$的连接(其中$F(0)="0"$,$F(1)="1"$)给出一个长度为$n$的$01$字符串$s$,询问$s$在$F(x)$
的所有子序列中出现了多少次。
$1≤n≤100$
$0≤x≤100$
Examples
Input
2 4
11
Output
14
Input
10 100
1010101010
Output
553403224
$f[i][l][r]$表示有多少$F[i]$的子序列里包含字符串[l,r]
有3种情况：
1.$l~r$都在$F[i-1]$中
2.$l~r$都在$F[i-2]$中
3.$l~k$在$F[i-1]$中,$k+1~r$都在$F[i-2]$中
对于第1种情况，如果$r=n$，那么$F[i-2]$就可以随便选
第二种情况也一样
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int Mod=1e9+;
int f[][][],len[],n,m;
char s[];
int qpow(int x,int y)
{
int res=;
while (y)
{
if (y&) res=1ll*res*x%Mod;
x=1ll*x*x%Mod;
y>>=;
}
return res;
}
int dfs(int x,int l,int r)
{int k;
if (f[x][l][r]!=-) return f[x][l][r];
if (x==||x==)
{
if (l==r&&s[l]==(char)(x+'')) return ;
return ;
}
int cnt=;
cnt+=1ll*dfs(x-,l,r)*((r==n)?qpow(,len[x-]):)%Mod;cnt%=Mod;
cnt+=1ll*dfs(x-,l,r)*((l==)?qpow(,len[x-]):)%Mod;cnt%=Mod;
for (k=l;k<r;k++)
{
cnt+=1ll*dfs(x-,l,k)*dfs(x-,k+,r)%Mod;
cnt%=Mod;
}
return f[x][l][r]=cnt;
}
int main()
{int i;
cin>>n>>m;
memset(f,-,sizeof(f));
len[]=;len[]=;
for (i=;i<=m;i++)
len[i]=(len[i-]+len[i-])%(Mod-);
cin>>s+;
printf("%d\n",dfs(m,,n));
}